{"id":687,"date":"2009-04-22T12:50:34","date_gmt":"2009-04-22T04:50:34","guid":{"rendered":"http:\/\/www.slyar.com\/blog\/?p=687"},"modified":"2022-07-03T15:47:19","modified_gmt":"2022-07-03T22:47:19","slug":"poj-1961-c","status":"publish","type":"post","link":"http:\/\/www.slyar.com\/blog\/poj-1961-c.html","title":{"rendered":"POJ 1961 Period C\u8bed\u8a00\u7248"},"content":{"rendered":"

\u6587\u7ae0\u4f5c\u8005\uff1a\u59dc\u5357(Slyar) <\/span>\u6587\u7ae0\u6765\u6e90\uff1aSlyar Home (www.slyar.com<\/a>) \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff0c\u8c22\u8c22\u5408\u4f5c\u3002<\/p>\n

<\/p>\n

Description<\/span><\/p>\n

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.<\/p>\n

Input<\/span><\/p>\n

The input consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) \u2013 the size of the string S.The second line contains the string S. The input file ends with a line, having the
\nnumber zero on it.<\/p>\n

Output<\/span><\/p>\n

For each test case, output \"Test case #\" and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.<\/p>\n

Sample Input<\/span><\/p>\n

3
\naaa
\n12
\naabaabaabaab
\n0<\/p>\n

Sample Output<\/span><\/p>\n

Test case #1
\n2 2
\n3 3<\/p>\n

Test case #2
\n2 2
\n6 2
\n9 3
\n12 4<\/p>\n

Slyar:\u8bf4\u4e0b\u9898\u76ee\u5927\u610f\u3002\u7ed9\u5b9a\u5b57\u7b26\u4e32S\uff0c\u6c42\u5176\u524dn\u4f4d\u91cd\u590d\u7684\u6b21\u6570\u3002\u6bd4\u5982aabaabaabaab\uff0c\u524d2\u4f4d\u662faa\uff0ca\u91cd\u590d\u4e862\u6b21\uff0c\u524d6\u4f4d\u662faabaab\uff0caab\u91cd\u590d\u4e862\u6b21\uff0c\u524d9\u4f4d\u662faabaabaab\uff0caab\u91cd\u590d\u4e863\u6b21\uff0c\u524d12\u4f4d\u662faabaabaabaab\uff0caab\u91cd\u590d\u4e864\u6b21\u3002<\/span><\/p>\n

\u672c\u9898\u662fPOJ 2406\u7684\u52a0\u5f3a\u7248\uff0c\u5229\u7528\u7684\u4f9d\u65e7\u662fKMP\u7b97\u6cd5\u3002\u6211\u4eec\u53ef\u4ee5\u5148\u8003\u8651\u53ea\u6709\u4e00\u7ec4\u6a21\u5f0f\u4e32\u7684\u60c5\u51b5\uff0c\u7136\u540e\u7528\u4e00\u4e2a\u5faa\u73af\u4f9d\u6b21\u5c1d\u8bd5\u4e0d\u540c\u957f\u5ea6\u7684\u6a21\u5f0f\u4e32\u5373\u53ef\u3002<\/span><\/p>\n

\u8fd9\u91cc\u6709\u4e00\u7bc7\u6211\u5199\u7684KMP\u5b66\u4e60\u5fc3\u5f97\uff0c\u53ef\u4ee5\u9002\u5f53\u53c2\u8003\u3002<\/span><\/p>\n

\/\/www.slyar.com\/blog\/kmp.html<\/a><\/p>\n

\r\n#include \r\n#include \r\n\r\n#define MAX 1000001\r\n\r\nint next[MAX];\r\nchar s[MAX];\r\n\r\nint main()\r\n{\r\n    int i, j, n, k;\r\n    k = 1;\r\n    while(1)\r\n    {\r\n        scanf(\"%d\", &n);\r\n        if (n == 0) break;\r\n        scanf(\"%s\", &s);\r\n        i = 0;\r\n        j = -1;\r\n        next[0] = -1;\r\n        while(i < n)\r\n        {\r\n            if (j == -1 || s[i] == s[j])\r\n            {\r\n                i++;\r\n                j++;\r\n                next[i] = j;\r\n            }\r\n            else\r\n            {\r\n                j = next[j];\r\n            }\r\n        }\r\n        printf(\"Test case #%d\\n\", k++);\r\n        \/* \u6328\u4e2a\u8bd5\u9a8c *\/\r\n        for (i = 2; i <= n; i++)\r\n        {\r\n            \/* \u8ba1\u7b97\u9996\u5c3e\u91cd\u590d\u5b50\u4e32\u7684\u957f\u5ea6 *\/\r\n            j = i - next[i];\r\n            \/* \u4e32\u6ee1\u8db3\u91cd\u590d\u6027\u8d28\u4e14\u91cd\u590d\u5b50\u4e32\u4e0d\u4e3a\u672c\u8eab *\/\r\n            if (i % j == 0 && i \/ j > 1)\r\n            {\r\n                printf(\"%d %d\\n\", i, i \/ j);\r\n            }\r\n        }\r\n        printf(\"\\n\");\r\n    }\r\n    return 0;\r\n}\r\n<\/pre>\n
\u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff1aSlyar Home<\/a> » POJ 1961 Period C\u8bed\u8a00\u7248<\/a><\/p>","protected":false},"excerpt":{"rendered":"
\u6587\u7ae0\u4f5c\u8005\uff1a\u59dc\u5357(Slyar) \u6587\u7ae0\u6765\u6e90\uff1aSlyar Home (www.slyar.com) \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff0c\u8c22\u8c22\u5408\u4f5c\u3002 \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff1aSlyar Home » POJ 1961 Period C\u8bed\u8a00\u7248<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1103],"tags":[258],"class_list":["post-687","post","type-post","status-publish","format-standard","hentry","category-acm-oj-solution","tag-258"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t