字符串

next数组 与 KMP

\(O(n+m)\)

//next
void getNext(char *p, int *next) {
    next[0] = -1;
    int i = 0, j = -1;
    while(i < strlen(p))
        if(j == -1 || p[i] == p[j]){
            i++, j++;
            next[i] = j;
        }
        else j = next[j];
}
//KMP
//主体字符串 匹配字符串
int KMP(char *s, char *p){
    int i = 0;
    int j = 0;
    while(i < strlen(s) && j < strlen(p))
        if(j == -1 || s[i] == p[j]) i++, j++;
        else j = next[j];
    //返回存在与 p 相同的字串的位置
    if(j == strlen(p)) return i-j;
    else return -1;
}

Manacher

\(O(n)\)

//Manacher
int Manacher(string s){
    if(s.length() == 0) return 0;
    int len = (int)(s.length()*2-1);
    char *cArry = new char[len];
    int *pArry = new int[len];
    //预处理：全都变成奇数回文串
    for(int i = 0; i < len; i++)
        cArry[i] = i&1 ? s[(i-1)/2] : '#';
    //R:最右右边界  C：与R对应的回文中心 maxn：最大回文半径，返回值为maxn-1
    //R实际上是最右边界的右边一位
    int R = -1;
    int C = -1;
    int maxn = 0;
    for(int i = 0; i < len; i++){
        pArry[i] = i >= R ? 1 : min(R-i, pArry[2*C-i]); //取得可能的最短的回文半径 *R是最右边界的右边一位 
        //暴力计算
        while(i+pArry[i] < len && i-pArry[i] > -1){
            if(cArry[i+pArry[i]] == cArry[i-pArry[i]]) pArry[i]++;
            else break;
        }
        //更新
        if(i+pArry[i] > R){
            R = i+pArry[i];
            C = i;
        }
        maxn = maxn(pArry[i], maxn);
    }
    //清空动态数组
    delete[] cArry;
    delete[] pArry;

    return maxn-1;
}

最小表示法

\(O(n)\)

//最小表示法
int min_(char *s){
    int k = 0, i = 0, j = 1, len = strlen(s); // k:匹配长度
    while(k < len && i < len && j < len){
        if(s[(s+k)%len] == s[(j+k)%len]) k++; 
        else {
            s[(s + k) % len] > s[(j + k) % len] ? i = i+k+1 : j = j+k+1;//不同则跳转
            if(i == j) i++;  //若跳转后不同，要保证比较的双方不同
            k = 0;
        } 
    }
    return min(i, j);
}