题解

1 条题解

  • 1
    @ 2022-08-14 11:55:37
    #include <cstdio>
    #include <cstring>
    using namespace std;
    char s2[1000001];
    int nxt[1000001] = {0};
    void getnext(int m) {
        int j = 0;
    
        for (int i = 2; i <= m; i++) {
            while (j != 0 && s2[j + 1] != s2[i])
                j = nxt[j];
    
            if (s2[j + 1] == s2[i])
                j++;
    
            nxt[i] = j;
        }
    
        return;
    }
    int main() {
        while (scanf("%s", s2 + 1) != EOF) {
            if (s2[1] == '.')
                break;
    
            memset(nxt, 0, sizeof(nxt));
            int m = strlen(s2 + 1);
            getnext(m);
            int ans = 1;
    
            if (m % (m - nxt[m]) == 0) {
                ans = m / (m - nxt[m]);
            }
    
            printf("%d\n", ans);
        }
    
        return 0;
    }
    
  • 1

信息

ID
1516
难度
10
分类
KMP字符串 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者