0x15 字符串

KMP算法

next数组的求法

void calc_next() {

    next[]=;

    for (int i=, j=; i<=n; ++i) {

        while (j>&&a[i]!=a[j+]) j=next[j];

        if (a[i]==a[j+]) ++j;

        next[i]=j;

    }

}

f数组的求法

void calc_next() {

    for (int i=, j=; i<=m; ++i) {

        while (j> && (j==n || b[i]!=a[j+])) j=next[j];

        if (b[i]==a[j+]) ++j;

        f[i]=j;

        //if (f[i]==n) //此时就是A在B中的某一次出现

    }

}

【例题】POJ1961 Period

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 #define next nxt

 using namespace std;

 const int INF=0x3f3f3f3f;

 const int maxn=+;

 char a[maxn];

 int next[maxn], n, T;

 void calc_next() {

     next[]=;

     for (int i=, j=; i<=n; ++i) {

         while (j>&&a[i]!=a[j+]) j=next[j];

         if (a[i]==a[j+]) ++j;

         next[i]=j;

     }

 }

 int main() {

     //freopen("a.txt", "r", stdin);

     //freopen("a.out", "w", stdout);

     int kase=;

     while (cin>>n&&n) {

         scanf("%s", a+);

         calc_next();

         printf("Test case #%d\n", ++kase);

         for (int i=; i<=n; ++i) {

             if (i%(i-next[i])== && i/(i-next[i])>)

                 printf("%d %d\n", i, i/(i-next[i]));

         }

         printf("\n");

     }

     return ;

 }  

最小表示法

    n=strlen(s+);

    for (int i=; i<=n; ++i) s[n+i]=s[i];

    int i=, j=, k;

    while (i<=n&&j<=n) {

        for (k=; k<n&&s[i+k]==s[j+k]; ++k);

        if (k==n) break;

        if (s[i+k]>s[j+k]) {

            i=i+k+;

            if (i==j) ++i;

        }

        else {

            j=j+k+;

            if (i==j) ++j;

        }

    }

    int ans=min(i, j);