poj 1961

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 1e6 + 10;
int n;
int ne[N];
char p[N];

int main() 
{
    int n;
    int ca = 1;
    while(cin >> n && n)
    {
        cin >> p + 1;
        printf("Test case #%d\n", ca ++);
        for(int i = 2, j = 0; i <= n; i ++)
        {
            while(j && p[i] != p[j + 1])    j = ne[j];
            if(p[i] == p[j + 1])    j ++;
            ne[i] = j;
        }
        for(int i = 2; i <= n; i ++)
        {
            int cycle_len = i - ne[i];
            int num = i / cycle_len;
            if(i % cycle_len == 0 && num != 1)
                printf("%d %d\n", i, num);
        }
        cout << endl;
    }
    return 0;
}

hdoj 3746

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;

const int N = 1e6 + 10;
int n;
int ne[N];
char p[N];

int main() 
{
    int T;
    cin >> T;
    while(T --)
    {
        scanf("%s", p + 1);
        int L = strlen(p + 1);
        for(int i = 2, j = 0; i <= L; i ++)
        {
            while(j && p[i] != p[j + 1])    j = ne[j];
            if(p[i] == p[j + 1])    j ++;
            ne[i] = j;
        }
        int len = L - ne[L];
        if(L % len == 0)
        {
            cout << (len == L ? L : 0) << endl;
        }
        else
        {
            cout << len - L % len << endl;
        }
    }
    return 0;
}

poj 2406

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;

int ne[N];
char p[N];

int main() 
{
    while(scanf("%s", p + 1)) {
        if(p[1] == '.') {
            break;
        }
        int L = strlen(p + 1);
        for(int i = 2, j = 0; i <= L; i ++)
        {
            while(j && p[i] != p[j + 1])    j = ne[j];
            if(p[i] == p[j + 1])    j ++;
            ne[i] = j;
        }
        int ans = 1;
        if(L % (L - ne[L]) == 0) {
            ans = L / (L - ne[L]);
        }
        cout << ans << endl;
    }
    return 0;
}

poj 2752

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 4e5 + 10;

int ne[N];
char p[N];
int ans[N];
int cnt, len;

int main(){
    while(~ scanf("%s", p + 1)){
        len = strlen(p + 1);
        for(int i = 2, j = 0; i <= len; i ++)
        {
            while(j && p[i] != p[j + 1])    j = ne[j];
            if(p[i] == p[j + 1])    j ++;
            ne[i] = j;
        }
        cnt = 0;
        int t = ne[len];
        while(t){
            ans[cnt ++] = t;
            t = ne[t];
        }
        for(int i = cnt - 1; i >= 0; i --)
            printf("%d ", ans[i]);
        printf("%d\n", len);
    }
    return 0;
}