POJ2406 Power Strings 题解 KMP算法

题目链接：http://poj.org/problem?id=2406

题目大意：给你一个字符串 \(t\) ，\(t\) 可以表示为另一个小字符串循环了 \(K\) 了，求最大的循环次数 \(K\) 。

题目分析：设字符串长度为 \(m\) ，如果 \(m-1-nxt[m-1]\) 能够整除 \(m\) ，则 \(K=m/(m-1-nxt[m-1])\) ，否则 \(K=1\) 。

实现代码如下：

#include <cstdio>

#include <string>

using namespace std;

const int maxn = 1001000;

int m, nxt[maxn];

string t;

char ch[maxn];

string read() {

    scanf("%s", ch);

    string tmp_s = ch;

    return tmp_s;

}

void cal_next() {

    m = t.length();

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

        while (j != -1 && t[j+1] != t[i]) j = nxt[j];

        nxt[i] = (j+1 < i && t[j+1] == t[i]) ? ++j : -1;

    }

}

int main() {

    while (true) {

        t = read();

        if (t == ".") break;

        cal_next();

        int K = 1;

        if (m % (m-1-nxt[m-1]) == 0) {

            K = m / (m-1-nxt[m-1]);

        }

        printf("%d\n", K);

    }

    return 0;

}

作者：zifeiy

巴特西

POJ2406 Power Strings 题解 KMP算法

最新文章

热门文章