进阶1:KMP算法,Manacher算法,BFPRT算法

程序1:KMP算法

#include<iostream>   //KMP算法
using namespace std;
#include<string>
#include<typeinfo>

int* getNextArray(string str2)
{
    if(str2.length()==1)
    {
        int* next= new int[1];
        next[0] = -1;
        return next;
    }
    int* next = new int[str2.length()];//注意数组在函数结束返回时只返回一个指针,所以需要将数组开辟在堆区
    next[0]=-1;
    next[1]=0;
    int i=2;
    int cn=0;
    while(i<str2.length())
    {
        if(str2[i-1]==str2[cn])
        {
            next[i++]=++cn;
        }
        else if(cn>0)
        {
            cn=next[cn];
        }
        else
        {
            next[i++]=0;
        }
    }
    return next;
}
int getIndexOf(string str1,string str2)
{
    if(str1.empty() || str2.empty() || str2.length()<1 || str1.length() < str2.length())
    {
        return -1;
    }
    int i1=0;
    int i2=0;
    int* next = getNextArray(str2);
    while(i1<str1.length()&&i2<str2.length())
    {
        if(str1[i1] == str2[i2])
        {
            i1++;
            i2++;
        }
        else if(next[i2]==-1)
        {
            i1++;
        }
        else
        {
            i2=next[i2];
        }
    }
    return i2 == str2.length()?i1-i2:-1;
}

int main()
{
    string s1 = "gjfhgihgibbvkl";
    string s2 = "gihgib";
    cout<<getIndexOf(s1,s2);
    return 0;
}

程序2:Manacher算法

#include<iostream>    //Manacher算法
using namespace std;
#include<string>
#include<typeinfo>
#include<vector>

string manacherString(string str)
{
    string res;
    for(int i =0;i<str.length();i++)
    {
       res+="#";
       res+=str[i];
    }
    res+="#";
    return res;
}

int maxLcpsLength(string str)
{
    if(str.length() == 0)
    {
        return 0;
    }
    string stringArr = manacherString(str);
    int parr[stringArr.length()];  // 回文半径数组
    int C = -1;
    int R = -1;
    int maxD = INT16_MIN;
    for(int i=0;i!=stringArr.length();i++)
    {
        parr[i] = R>i?min(R-i,parr[2*C-i]):1;
        while(i+parr[i] < stringArr.length() && i-parr[i]>-1)
        {
            if(stringArr[i+parr[i]]==stringArr[i-parr[i]])
            {
                parr[i]++;
            }
            else
                break;
        }
        if(i+parr[i]>R)
        {
            R=i+parr[i];
            C=i;
        }
        maxD = max(parr[i],maxD);        
    }
    return maxD-1;
}


int main()
{
    string a = "abcdcbatttabcdc";
    int res = maxLcpsLength(a);
    cout<<res;

    return 0;
}

应用:

#include<iostream>    //Manacher算法的应用
using namespace std;
#include<string>
#include<typeinfo>
#include<vector>

string manacherString(string str)
{
    string res;
    for(int i =0;i<str.length();i++)
    {
       res+="#";
       res+=str[i];
    }
    res+="#";
    return res;
}

string maxLcpsLength(string str)
{
    if(str.length() == 0)
    {
        return 0;
    }
    string stringArr = manacherString(str);
    int parr[stringArr.length()];  // 回文半径数组
    int C = -1;
    int R = -1;
    int maxContainsEnd = -1;
    string res;
    for(int i=0;i!=stringArr.length();i++)
    {
        parr[i] = R>i?min(R-i,parr[2*C-i]):1;
        while(i+parr[i] < stringArr.length() && i-parr[i]>-1)
        {
            if(stringArr[i+parr[i]]==stringArr[i-parr[i]])
            {
                parr[i]++;
            }
            else
                break;
        }
        if(i+parr[i]>R)
        {
            R=i+parr[i];
            C=i;
        }
        if(R==stringArr.length())
        {
            maxContainsEnd = parr[i];
            break;
        } 
    }
    for(int i=0;i<str.length()-maxContainsEnd+1;i++)
    {
        res+=stringArr[i*2+1];
    }
    return res;
}


int main()
{
    string a = "abcd12321";
    string res = maxLcpsLength(a);
    for(int i=0;i<res.length();i++)
    {
        cout<<res[i];
    }

    return 0;
}

程序3:BFPRT算法

#include<iostream>   //BFPRT算法
using namespace std;
#include<string>
#include<typeinfo>
#include<vector>
#include<algorithm>

int getMdeian(int* arr,int begin,int end)
{
    sort(arr+begin,arr+end);
    int sum = end+begin;
    int mid = (sum / 2)+(sum % 2);
    return arr[mid];
}
void swap(int* arr,int small,int cur)
{
    int tmp = arr[small];
    arr[small] = arr[cur];
    arr[cur]=tmp;
}
int* partition(int*arr,int begin,int end,int pivot)
{
    int small=begin-1;
    int cur = begin;
    int big = end+1;
    while(cur!=big)
    {
        if(arr[cur]<pivot)
        {
            swap(arr,++small,cur++);
        }
        else if(arr[cur]>pivot)
        {
            swap(arr,--big,cur);
        }
        else
            cur++;
    }
    int* range =new int[2];
    range[0]=small+1;
    range[1]=big-1;
    return range;
}
int bfprt(int *arr,int begin,int end,int i);   //进行声明
int medianOfMedians(int* arr,int begin,int end)
{
    int num = end-begin+1;
    int offset = num%5==0?0:1;
    int mArr[num /5 +offset];
    for(int i =0;i<num/5+offset;i++)
    {
        int beginI=begin+i*5;
        int endI = beginI+4;
        mArr[i] = getMdeian(arr,beginI,min(end,endI));
    }
    return bfprt(mArr,0,num/5+offset-1,(num/5+offset)/2);
}

int bfprt(int *arr,int begin,int end,int i)
{
    if(begin ==end)
    {
        return arr[begin];
    }
    int pivot = medianOfMedians(arr,begin,end);  //中位数数组中的中位数作为划分值
    int* pivotRange = partition(arr,begin,end,pivot);  //以pivot为划分值返回等于区域的范围
    if(i>=pivotRange[0]&&i<=pivotRange[1])
    {
        return arr[i];
    }
    else if(i<pivotRange[0])
    {
        return bfprt(arr,begin,pivotRange[0]-1,i);
    }
    else 
        return bfprt(arr,pivotRange[1]+1,end,i);
}

int* copyArray(int* arr,int len)   //将原数组拷贝
{
    int* res = new int[len];
    for(int i=0;i<len;i++)
    {
        res[i] = arr[i];
    }
    return res;
}
int getMinKthByBFPRT(int *arr,int len,int K)
{
    int *copyArr = copyArray(arr,len);
    return bfprt(arr,0,len-1,K-1);
}

int main()
{
    int a[]={1,8,9,6,2,4,3,7,5,4,3};
    cout<<getMinKthByBFPRT(a,11,8);
    return 0;
}