{"id":686,"date":"2009-04-22T12:40:27","date_gmt":"2009-04-22T04:40:27","guid":{"rendered":"http:\/\/www.slyar.com\/blog\/?p=686"},"modified":"2022-07-03T15:47:19","modified_gmt":"2022-07-03T22:47:19","slug":"poj-2406-c","status":"publish","type":"post","link":"http:\/\/www.slyar.com\/blog\/poj-2406-c.html","title":{"rendered":"POJ 2406 Power Strings 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

Given two strings a and b we define a*b to be their concatenation. For example, if a = \"abc\" and b = \"def\" then a*b = \"abcdef\". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = \"\" (the empty string) and a^(n+1) = a*(a^n).<\/p>\n

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

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.<\/p>\n

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

For each s you should print the largest n such that s = a^n for some string a.<\/p>\n

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

abcd
\naaaa
\nababab
\n.<\/p>\n

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

1
\n4
\n3<\/p>\n

Slyar:\u8bf4\u4e00\u4e0b\u9898\u76ee\u5927\u610f\u3002a\u662f\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u8bb0s=a^n\u4e3aa\u91cd\u590dn\u6b21\u6240\u5f62\u6210\u7684\u5b57\u7b26\u4e32\u3002\u6bd4\u5982\u8bf4a\u662fabcd\uff0c\u90a3\u4e48\u5f53n=3\u65f6\uff0ca^3\u5c31\u662fabcdabcdabcd\u3002\u73b0\u5728\u7ed9\u51fa\u5b57\u7b26\u4e32s\uff0c\u6c42\u51fa\u6700\u5927\u7684\u91cd\u590d\u6b21\u6570n\u3002<\/span><\/p>\n

\u672c\u9898\u5229\u7528\u7684\u8fd8\u662fKMP\u6a21\u5f0f\u5339\u914d\u7b97\u6cd5\uff0c\u5f53\u7136\u4f60\u9700\u8981\u771f\u6b63\u7406\u89e3Next[i]\u7684\u542b\u4e49\u624d\u53ef\u4ee5\u81ea\u5df1\u5199\u51fa\u4ee3\u7801\uff0c\u6211\u5728\u8fd9\u91cc\u7ea0\u7ed3\u4e86\u5f88\u4e45...<\/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, len;\r\n    while(1)\r\n    {\r\n        scanf(\"%s\", s);\r\n        if (strcmp(s, \".\") == 0) break;\r\n        len = strlen(s);\r\n        i = 0;\r\n        j = -1;\r\n        next[0] = -1;\r\n        while(i < len)\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        \/* \u8ba1\u7b97\u9996\u5c3e\u91cd\u590d\u5b50\u4e32\u7684\u957f\u5ea6 *\/\r\n        j = i - next[i];\r\n        printf(\"%d %d %d\\n\", i, next[i], j);\r\n        \/* \u82e5\u4e32\u6ee1\u8db3\u91cd\u590d\u6027\u8d28\uff0c\u5219i%j==0\uff1b\u5426\u5219\u91cd\u590d\u5b50\u4e32\u4e3a\u672c\u8eab *\/\r\n        if (i % j == 0) k = i \/ j;\r\n        else k = 1;\r\n        printf(\"%d\\n\", k);\r\n    }\r\n    return 0;\r\n}\r\n<\/pre>\n
\u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff1aSlyar Home<\/a> » POJ 2406 Power Strings 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 2406 Power Strings 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-686","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