2016 UESTC Training for Search Algorithm & String K – 卿大爷的三个女友 KMP、跳转数组

  Source

2016 UESTC Training for Search Algorithm & String

  My Solution

#include
#include
#include
using namespace std;
const int maxn=1e5 + 8;

int nxt[maxn], len;
char text[maxn];
void getnxt(char *p)
{
    nxt[1] = 0;
    for(int i = 1, j = 0; i < len; i++){
        j = nxt[i];
        while(j && p[j] != p[i])
            j = nxt[j];
        nxt[i+1] = p[j] == p[i] ? j+1 : 0;            //在这里进行初始化了， 故用的时候不要memset了
    }
}

bool kmp(char *T,char *P,int n,int m)
{
    for(int i=0, j=0; i < n; i++){ while(j && P[j] != T[i]) j = nxt[j]; if(P[j] == T[i]) j++; if(j == m) return true; } return false; } int main() { #ifdef LOCAL freopen("a.txt", "r", stdin); #endif // LOCAL int T,j,ans; scanf("%d",&T); while(T--){ ans=0; scanf("%s",text); len=strlen(text); getnxt(text); j = nxt[len]; while(j){ if(len >= 3*j&& kmp(text+j, text, len-2*j, j)){
                ans=j;
                break;
            }
            j = nxt[j];
        }
        printf("%dn",ans);
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx