POJ 2406

Power String

这道题的大意是：

给出若干字符串，求每个字符串的最小构成子串（从字符串的头开始），即由该子串不断重复能构成所给出的字符串。

主要是kmp的应用。

首先，使用暴力的方法能过。时间复杂度高，空间复杂度低。 枚举子串的长度，该长度应能被整个字符串的长度整除。将子串与字符串遍历比较，若有不同则枚举下一个子串。对子串可以用加一模除整个子串长度，来扩展成语字符串相同的长度。

#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdio.h>
const int max = 10000001;
char Str[max];

int main() {
    while (scanf("%s", Str) && Str[0] != '.') {
        int chnum = 1;
        int len = strlen(Str);

        for (chnum = 1; chnum <= len; chnum++) {
            int cishu = len%chnum;
            if (cishu) continue;
            if (chnum == len) {
                printf("1\n");
                break;
            }

            int i = 0, j = 0;
            for (i = 0; i < len; i++) {
                if (Str[i] != Str[j]) break;
                else j = (j+1)%chnum;
            }

            if (i >= len) {
                printf("%d\n", len/chnum);
                break;
            }
        }
    }
    return 0;
}

可以用kmp算法中，构造next数组的思想。 next数组存放的是当前字符要与之比较的字符，在这两个字符之前的字符都相同。 当每个字符均不同时要特判。

#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdio.h>

const int max = 10000001;
char Str[max];
int next[max];
void get_next(int len) {
    int i = 0, j = -1;
    next[0] = -1;
    while(i < len) {
        if (j == -1 || Str[i] == Str[j]) {
            ++i; ++j;
            next[i] = j;
        }
        else j = next[j];
    }   
    return;
}

int main() {
    while (scanf("%s", Str) && Str[0] != '.') {
        int len = strlen(Str);
        get_next(len);
        int num = len-next[len];
        if (len%(num) == 0) printf("%d\n", len/(num));
        else printf("1\n");
    }
    return 0;
}