{"id":47,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-7-31\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-7-31","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-7-31\/","title":{"rendered":"2020-7-31"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=1459&pid=0<\/a><\/p>\n

<\/a>\u9898\u76ee<\/h4>\n

\u8fd9\u662f\u4e00\u9053\u6a21\u677f\u9898\u3002
\u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32A\u548c\u4e00\u4e2a\u5b57\u7b26\u4e32B\uff0c\u6c42B\u5728A\u4e2d\u7684\u51fa\u73b0\u6b21\u6570\u3002A\u548cB\u4e2d\u7684\u5b57\u7b26\u5747\u4e3a\u82f1\u8bed\u5927\u5199\u5b57\u6bcd\u6216\u5c0f\u5199\u5b57\u6bcd\u3002
A\u4e2d\u4e0d\u540c\u4f4d\u7f6e\u51fa\u73b0\u7684B\u53ef\u91cd\u53e0\u3002<\/p>\n

<\/a>\u8f93\u5165<\/h5>\n

\u8f93\u5165\u5171\u4e24\u884c\uff0c\u5206\u522b\u662f\u5b57\u7b26\u4e32A\u548c\u5b57\u7b26\u4e32B\u3002<\/p>\n

<\/a>\u8f93\u51fa<\/h5>\n

\u8f93\u51fa\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793aB\u5728A\u4e2d\u7684\u51fa\u73b0\u6b21\u6570\u3002<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
zyzyzyz\nzyz\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
3\n<\/code><\/pre>\n
<\/a>\u63d0\u793a<\/h4>\n
1\u2264A,B\u7684\u957f\u5ea6\u226410^6\uff0cA\u3001B\u4ec5\u5305\u542b\u5927\u5c0f\u5199\u5b57\u6bcd\u3002<\/p>\n
<\/a>\u89e3\u6790<\/h4>\n
\u8fd9\u662f\u4e00\u9053\u5b57\u7b26\u4e32\u54c8\u5e0c\u7684\u9898\u76ee<\/p>\n
#pragma<\/span> GCC optimize(1)<\/span>\n#pragma<\/span> GCC optimize(2)<\/span>\n#pragma<\/span> GCC optimize(3,\"Ofast\",\"inline\")<\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nconst<\/span> int<\/span> N=<\/span>1e6<\/span>+<\/span>500<\/span>;<\/span>\nchar<\/span> a[<\/span>N]<\/span>=<\/span>\"\"<\/span>;<\/span>\nchar<\/span> b[<\/span>N]<\/span>=<\/span>\"\"<\/span>;<\/span>\nint<\/span> base=<\/span>31<\/span>;<\/span>\nlong<\/span> long<\/span> p[<\/span>N]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nlong<\/span> long<\/span> h[<\/span>N]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nlong<\/span> long<\/span> sum1=<\/span>0<\/span>,<\/span>js1,<\/span>sum=<\/span>0<\/span>;<\/span>\nint<\/span> la=<\/span>1<\/span>,<\/span>lb=<\/span>1<\/span>;<\/span>\nchar<\/span> w;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    scanf<\/span>(<\/span>\"%s\"<\/span>,<\/span>a+<\/span>1<\/span>)<\/span>;<\/span>\n    scanf<\/span>(<\/span>\"%s\"<\/span>,<\/span>b+<\/span>1<\/span>)<\/span>;<\/span>\n    for<\/span>(<\/span>;<\/span>a[<\/span>la]<\/span>;<\/span>la++<\/span>)<\/span>;<\/span>\n    for<\/span>(<\/span>;<\/span>b[<\/span>lb]<\/span>;<\/span>lb++<\/span>)<\/span>;<\/span>\n    la--<\/span>;<\/span>\n    lb--<\/span>;<\/span>\n    p[<\/span>0<\/span>]<\/span>=<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>max<\/span>(<\/span>la,<\/span>lb)<\/span>;<\/span>i++<\/span>)<\/span>\n        p[<\/span>i]<\/span>=<\/span>p[<\/span>i-<\/span>1<\/span>]<\/span>*<\/span>base;<\/span> \t   \/\/\u8fdb\u5236<\/span>\n    if<\/span>(<\/span>a[<\/span>1<\/span>]<\/span>>=<\/span>'A'<\/span>&&<\/span>a[<\/span>1<\/span>]<\/span><=<\/span>'Z'<\/span>)<\/span>   \/\/\u5224\u65ad\u5927\u5c0f\u5199<\/span>\n        w=<\/span>'A'<\/span>;<\/span>\n    else<\/span>\n        w=<\/span>'a'<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>la;<\/span>i>=<\/span>1<\/span>;<\/span>i--<\/span>)<\/span>\n        h[<\/span>i]<\/span>=<\/span>h[<\/span>i+<\/span>1<\/span>]<\/span>*<\/span>base+<\/span>a[<\/span>i]<\/span>-<\/span>w+<\/span>1<\/span>;<\/span> \/\/\u6c42a\u5b57\u7b26\u4e32\u7684\u54c8\u5e0c\u6570\u7ec4<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>lb;<\/span>i>=<\/span>1<\/span>;<\/span>i--<\/span>)<\/span>\n        sum1=<\/span>sum1*<\/span>base+<\/span>b[<\/span>i]<\/span>-<\/span>w+<\/span>1<\/span>;<\/span>   \/\/\u6c42b\u5b57\u7b26\u4e32\u7684\u54c8\u5e0c<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>1<\/span>;<\/span>i<=<\/span>la-<\/span>lb+<\/span>3<\/span>;<\/span>i++<\/span>)<\/span>    \/\/\u6ce8\u610fi\u5fc5\u987b\u5c0f\u4e8e\u7b49\u4e8ela-lb \u5426\u5219\u6570\u7ec4\u4f1a\u8d8a\u754c<\/span>\n    {<\/span>\n        js1=<\/span>h[<\/span>i]<\/span>-<\/span>h[<\/span>i+<\/span>lb]<\/span>*<\/span>p[<\/span>lb]<\/span>;<\/span>    \/\/\u5224\u65ad\u662f\u5426\u76f8\u7b49<\/span>\n        if<\/span>(<\/span>js1==<\/span>sum1)<\/span>\n            sum+<\/span>=<\/span>1<\/span>;<\/span>\n    }<\/span>\n    cout<<<\/span>sum<<<\/span>endl;<\/span>\n}<\/span>\n\n<\/code><\/pre>\n
<\/a>\u9898\u76ee<\/h4>\n
Given two strings a and b we define a * b to be their concatenation. For example, if a = \u201cabc\u201d and b = \u201cdef\u201d then a * b = \u201cabcdef\u201d. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = \u201c\u201d (the empty string) and a^(n+1) = a*(a^n).<\/p>\n
<\/a>\u8f93\u5165<\/h4>\n
Each test case is a line of input representing s, a string of printable characters.<\/p>\n
<\/a>\u8f93\u51fa<\/h4>\n
For each s you should print the largest n such that s = a^n for some stringa. 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
<\/a>\u6837\u4f8b\u8f93\u5165<\/h4>\n
abcd\naaaa\nababab\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h4>\n
1\n4\n3\n<\/code><\/pre>\n
<\/a>\u89e3\u6790<\/h4>\n
KMP\u7b97\u6cd5\u7684\u5e94\u7528<\/p>\n
#pragma<\/span> GCC optimize(1)<\/span>\n#pragma<\/span> GCC optimize(2)<\/span>\n#pragma<\/span> GCC optimize(3,\"Ofast\",\"inline\")<\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nconst<\/span> ll mod=<\/span>1e9<\/span>+<\/span>7<\/span>;<\/span>\nconst<\/span> ll N =<\/span> 1005000<\/span>;<\/span>\nll Next[<\/span>N]<\/span>;<\/span>\nchar<\/span> s[<\/span>N]<\/span>;<\/span>\nchar<\/span> t[<\/span>N]<\/span>;<\/span>\nll  tlen,<\/span>len;<\/span>\nvoid<\/span> getNext<\/span>(<\/span>char<\/span> s[<\/span>N]<\/span>)<\/span>\n{<\/span>\n    ll j=<\/span>0<\/span>,<\/span>k=<\/span>-<\/span>1<\/span>;<\/span>\n    Next[<\/span>0<\/span>]<\/span>=<\/span>-<\/span>1<\/span>;<\/span>\n    while<\/span>(<\/span>j<<\/span>tlen)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>k==<\/span>-<\/span>1<\/span>||<\/span>s[<\/span>j]<\/span>==<\/span>s[<\/span>k]<\/span>)<\/span>\n        {<\/span>\n            Next[<\/span>++<\/span>j]<\/span>=<\/span>++<\/span>k;<\/span>\n        }<\/span>\n        else<\/span>\n            k=<\/span>Next[<\/span>k]<\/span>;<\/span>\n    }<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    while<\/span>(<\/span>1<\/span>)<\/span>\n    {<\/span>\n        scanf<\/span>(<\/span>\"%s\"<\/span>,<\/span>s)<\/span>;<\/span>\n        if<\/span>(<\/span>s[<\/span>0<\/span>]<\/span>==<\/span>'.'<\/span>)<\/span>\n        break<\/span>;<\/span>\n        tlen=<\/span>strlen<\/span>(<\/span>s)<\/span>;<\/span>\n        len=<\/span>tlen;<\/span>\n        getNext<\/span>(<\/span>s)<\/span>;<\/span>\n        ll kk=<\/span>tlen-<\/span>Next[<\/span>tlen]<\/span>;<\/span>\n        if<\/span>(<\/span>strlen<\/span>(<\/span>s)<\/span>%<\/span>kk==<\/span>0<\/span>)<\/span>\n        {<\/span>\n            printf<\/span>(<\/span>\"%dn\"<\/span>,<\/span>strlen<\/span>(<\/span>s)<\/span>\/<\/span>kk)<\/span>;<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span> \n            printf<\/span>(<\/span>\"1n\"<\/span>)<\/span>;<\/span>   \/\/\u5982\u679c\u4e0d\u80fd\u9664\u5c3d\uff0c\u8bf4\u660e\u6709\u540e\u7f00\uff0c\u4f8b\u5982abababa\uff0c\u8fd9\u79cd\u60c5\u51b5\u53ea\u80fd\u4e3a1<\/span>\n        }<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n<\/code><\/pre>\n
<\/a>\u9898\u76ee<\/h4>\n
\u5728CSP\u521d\u8d5b\u540e\uff0cchen03\u7684RP\u5feb\u7528\u5b8c\u4e86\u3002<\/p>\n
RP\u662f\u4e2a\u795e\u5947\u7684\u4e1c\u897f\u3002\u5177\u4f53\u6765\u8bf4\uff0cchen03\u7684RP\u503c\u53ef\u4ee5\u7528\u4e8c\u8fdb\u5236\u6b63\u6574\u6570a\u548c\u5341\u8fdb\u5236\u6b63\u6574\u6570n\u8868\u793a\u3002\u4ed6\u7684RP\u503c\u53ef\u4ee5\u8868\u793a\u4e3a
 RP=axor(a<<1)xor(a<<2)xor\u2026xor(a<<(n-1))\u3002<\/p>\n
\u5176\u4e2da<\n
chen03\u60f3\u77e5\u9053\u4ed6\u7684RP\u503c\u662f\u591a\u5c11\u3002<\/p>\n
\u6ce8\uff1a
 1.\u5c06a\u5de6\u79fbi\u4f4d\uff0c\u5373\u5728a\u540e\u6dfb\u52a0i\u4e2a0\uff0c\u4e5f\u53ef\u4ee5\u770b\u6210a\u00d72i\uff0c\u5728C++\u4e2d\u7684\u8fd0\u7b97\u7b26\u4e3a<<\uff1b
 2.\u6309\u4f4d\u5f02\u6216\uff1a\u5728\u4e8c\u8fdb\u5236\u4e0b\uff0c\u5bf9\u4e24\u4e2a\u6570\u7684\u6bcf\u4e00\u4f4d\u8fdb\u884c\u5f02\u6216\u8fd0\u7b97\uff0c\u5e76\u628a\u7ed3\u679c\u653e\u5230\u7b54\u6848\u7684\u5f53\u524d\u4f4d\u4e0a\uff0c\u5728C++\u4e2d\u7684\u8fd0\u7b97\u7b26\u4e3a^\u3002\u5f02\u6216\uff0c\u5373\u4e24\u4e2a\u503c\u540c\u4e3a1\u6216\u540c\u4e3a0\u65f6\u7ed3\u679c\u4e3a0\uff0c\u5426\u5219\u4e3a1\u3002<\/p>\n
<\/a>\u8f93\u5165<\/h3>\n
\u5171\u4e24\u884c\uff0c\u7b2c\u4e00\u884c\u4e00\u4e2a\u4e8c\u8fdb\u5236\u6b63\u6574\u6570 a\uff08\u4fdd\u8bc1\u4e0d\u542b\u524d\u5bfc 0\uff09\uff0c\u7b2c\u4e8c\u884c\u4e00\u4e2a\u5341\u8fdb\u5236\u6b63\u6574\u6570 n\uff0c\u610f\u4e49\u5982\u9898\u76ee\u63cf\u8ff0\u3002<\/p>\n
<\/a>\u8f93\u51fa<\/h4>\n
\u4e00\u884c\u4e00\u4e2a\u4e8c\u8fdb\u5236\u6b63\u6574\u6570\uff0c\u8868\u793a chen03 \u7684 RP \u503c\u3002\u7b54\u6848\u4e0d\u7528\u53d6\u6a21\u3002<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u5165<\/h4>\n
100001001\n4\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h4>\n
111101110111\n<\/code><\/pre>\n
<\/a>\u63d0\u793a<\/h4>\n
\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n
<\/a>\u89e3\u6790<\/h4>\n
\u9996\u5148\u5148\u7b80\u5355\u4ecb\u7ecd\u4e00\u4e0b\u5f02\u6216(xor)\uff0c\u5f02\u6216\u5171\u5206\u4e3a4\u79cd\u60c5\u51b5
 0\u5f02\u62161\u7b49\u4e8e1
 1\u5f02\u62160\u7b49\u4e8e1
 0\u5f02\u62160\u7b49\u4e8e0
 1\u5f02\u62161\u7b49\u4e8e0
 \u5f02\u6216\u6700\u540e\u7ed3\u679c\u53ea\u548c1\u7684\u4e2a\u6570\u6709\u5173\uff0c1\u4e3a\u5947\u6570\u4e2a\uff0c\u7ed3\u679c\u5c31\u4e3a1\uff0c1\u4e3a\u5076\u6570\u4e2a\uff0c\u7ed3\u679c\u5c31\u4e3a0\uff0c\u4f8b\u5982\uff1a
 0 xor 0 xor 0 xor 1 = 1
 0 xor 0 xor 1 xor 1 = 0
 0 xor 0 xor 0 xor 1 xor 1 = 0<\/p>\n
\u9898\u76ee\u662f\u6307\u5c06\u4e00\u4e2a2\u8fdb\u5236\u6570\u8fdb\u884c\u5411\u5de6\u79fb\u4f4d\u6c42\u5f02\u6216\u7ed3\u679c\uff0c\u4e0b\u56fe\u5c31\u662f\u5bf9\u6837\u4f8b\u7684\u89e3\u91ca\uff0c\u7b2c\u4e00\u4e8c\u4e09\u56db\u884c\u5206\u522b\u8868\u793a\u79fb\u52a8\u4e00\u4f4d\uff0c\u4e24\u4f4d\uff0c\u4e09\u4f4d\u548c\u56db\u4f4d\uff0c\u7136\u540e\u7edf\u8ba1\u6bcf\u4e00\u5217\u4e2d1\u7684\u6570\u76ee\uff0c\u5982\u679c1\u4e3a\u5947\u6570\u4e2a\uff0c\u7ed3\u679c\u5c31\u4e3a1\uff0c\u5426\u5219\u5c31\u4e3a0.\u3002\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"<\/p>\n
\u8fd9\u4e2a\u9898\u76ee\u53ef\u4ee5\u5206\u4e3a\u4e24\u79cd\u60c5\u51b5\uff0c\u6837\u4f8b\u662f\u5176\u4e2d\u7684\u4e00\u79cd\u60c5\u51b5\uff0cn\u7684\u6570\u76ee\u5c0f\u4e8e\u5b57\u7b26\u4e32\u7684\u957f\u5ea6\uff0c\u53e6\u4e00\u79cd\u60c5\u51b5\u662f\u5927\u4e8e\uff0c\u5982
 111
 5
 \u8fd9\u79cd\u60c5\u51b5\u53ef\u4ee5\u53d1\u73b0\u4e2d\u95f4\u90e8\u5206\u7684\u7ed3\u679c\u5168\u90e8\u76f8\u540c\uff0c\u5373\u5982\u4e0b\u56fe\u6240\u793a\uff1a
 \"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"
 \u7136\u540e\u76f4\u63a5\u6a21\u62df\u8fd9\u4e2a\u8fc7\u7a0b\uff0c\u6c42\u6bcf\u4e00\u5217\u4e2d1\u7684\u4e2a\u6570\u5373\u53ef\u3002<\/p>\n
<\/a>\u4ee3\u7801<\/h4>\n
#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nchar<\/span> a[<\/span>1005000<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> b[<\/span>1005000<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> c[<\/span>1005000<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> n;<\/span>\n    scanf<\/span>(<\/span>\"%s\"<\/span>,<\/span>&<\/span>a)<\/span>;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>n)<\/span>;<\/span>\n    int<\/span> m=<\/span>strlen<\/span>(<\/span>a)<\/span>;<\/span>\n    int<\/span> p=<\/span>n-<\/span>m;<\/span>\n    queue<<\/span>char<\/span>><\/span>w;<\/span>\n    int<\/span> sum1=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>a[<\/span>i]<\/span>;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>w.<\/span>size<\/span>(<\/span>)<\/span><<\/span>n)<\/span>\n        {<\/span>\n            w.<\/span>push<\/span>(<\/span>a[<\/span>i]<\/span>)<\/span>;<\/span>\n            if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'1'<\/span>)<\/span>\n                sum1++<\/span>;<\/span>\n            int<\/span> k1=<\/span>sum1%<\/span>2<\/span>;<\/span>\n            if<\/span>(<\/span>k1==<\/span>1<\/span>)<\/span>\n            {<\/span>\n                printf<\/span>(<\/span>\"1\"<\/span>)<\/span>;<\/span>\n            }<\/span>\n            else<\/span>\n            {<\/span>\n                printf<\/span>(<\/span>\"0\"<\/span>)<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            int<\/span> p=<\/span>w.<\/span>front<\/span>(<\/span>)<\/span>;<\/span>\n            w.<\/span>pop<\/span>(<\/span>)<\/span>;<\/span>\n            if<\/span>(<\/span>p==<\/span>'1'<\/span>)<\/span>\n                sum1--<\/span>;<\/span>\n            w.<\/span>push<\/span>(<\/span>a[<\/span>i]<\/span>)<\/span>;<\/span>\n            if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'1'<\/span>)<\/span>\n                sum1++<\/span>;<\/span>\n            int<\/span> k1=<\/span>sum1%<\/span>2<\/span>;<\/span>\n            if<\/span>(<\/span>k1==<\/span>1<\/span>)<\/span>\n            {<\/span>\n                printf<\/span>(<\/span>\"1\"<\/span>)<\/span>;<\/span>\n            }<\/span>\n            else<\/span>\n            {<\/span>\n                printf<\/span>(<\/span>\"0\"<\/span>)<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n    }<\/span>\n    for<\/span>(<\/span>int<\/span> i=<\/span>0<\/span>;<\/span>i<<\/span>p;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        int<\/span> k1=<\/span>sum1%<\/span>2<\/span>;<\/span>\n        if<\/span>(<\/span>k1==<\/span>1<\/span>)<\/span>\n        {<\/span>\n            printf<\/span>(<\/span>\"1\"<\/span>)<\/span>;<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            printf<\/span>(<\/span>\"0\"<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    while<\/span>(<\/span>w.<\/span>size<\/span>(<\/span>)<\/span>!=<\/span>1<\/span>)<\/span>\n    {<\/span>\n        int<\/span> p=<\/span>w.<\/span>front<\/span>(<\/span>)<\/span>;<\/span>\n        w.<\/span>pop<\/span>(<\/span>)<\/span>;<\/span>\n        if<\/span>(<\/span>p==<\/span>'1'<\/span>)<\/span>\n            sum1--<\/span>;<\/span>\n        int<\/span> k1=<\/span>sum1%<\/span>2<\/span>;<\/span>\n        if<\/span>(<\/span>k1==<\/span>1<\/span>)<\/span>\n        {<\/span>\n            printf<\/span>(<\/span>\"1\"<\/span>)<\/span>;<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            printf<\/span>(<\/span>\"0\"<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\n\n<\/code><\/pre>\n
<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n
The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm:<\/p>\n
Step1. Connect the father\u2019s name and the mother\u2019s name, to a new string S.
 Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).<\/p>\n
Example: Father=\u2018ala\u2019, Mother=\u2018la\u2019, we have S = \u2018ala\u2019+\u2018la\u2019 = \u2018alala\u2019. Potential prefix-suffix strings of S are {\u2018a\u2019, \u2018ala\u2019, \u2018alala\u2019}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)<\/p>\n
<\/a>\u8f93\u5165<\/h5>\n
The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.
 Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.<\/p>\n
<\/a>\u8f93\u51fa<\/h5>\n
For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby\u2019s name.<\/p>\n
<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
ababcababababcabab\naaaaa\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
2 4 9 18\n1 2 3 4 5\n<\/code><\/pre>\n
<\/a>\u89e3\u6790<\/h5>\n
kmp\u7b97\u6cd5next\u6570\u7ec4\u7684\u5e94\u7528<\/p>\n
#include<\/span><\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\nchar<\/span> a[<\/span>500500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> Next[<\/span>500500<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nint<\/span> getNext<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> i=<\/span>0<\/span>,<\/span>j=<\/span>-<\/span>1<\/span>;<\/span>\n    Next[<\/span>0<\/span>]<\/span>=<\/span>-<\/span>1<\/span>;<\/span>\n    while<\/span>(<\/span>a[<\/span>i]<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>j==<\/span>-<\/span>1<\/span>||<\/span>a[<\/span>i]<\/span>==<\/span>a[<\/span>j]<\/span>)<\/span>\n        {<\/span>\n            i++<\/span>;<\/span>\n            j++<\/span>;<\/span>\n            Next[<\/span>i]<\/span>=<\/span>j;<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            j=<\/span>Next[<\/span>j]<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    while<\/span>(<\/span>scanf<\/span>(<\/span>\"%s\"<\/span>,<\/span>a)<\/span>!=<\/span>EOF<\/span>)<\/span>\n    {<\/span>\n        getNext<\/span>(<\/span>)<\/span>;<\/span>\n        int<\/span> k=<\/span>strlen<\/span>(<\/span>a)<\/span>;<\/span>\n        stack<<\/span>int<\/span>><\/span>w;<\/span>\n        while<\/span>(<\/span>k>=<\/span>1<\/span>)<\/span>\n        {<\/span>\n            w.<\/span>push<\/span>(<\/span>k)<\/span>;<\/span>\n            k=<\/span>Next[<\/span>k]<\/span>;<\/span>\n        }<\/span>\n        while<\/span>(<\/span>!<\/span>w.<\/span>empty<\/span>(<\/span>)<\/span>)<\/span>\n        {<\/span>\n            if<\/span>(<\/span>w.<\/span>size<\/span>(<\/span>)<\/span>==<\/span>1<\/span>)<\/span>\n                cout<<<\/span>w.<\/span>top<\/span>(<\/span>)<\/span><<<\/span>endl;<\/span>\n            else<\/span>\n                cout<<<\/span>w.<\/span>top<\/span>(<\/span>)<\/span><<<\/span>' '<\/span>;<\/span>\n            w.<\/span>pop<\/span>(<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-47","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/47","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=47"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/47\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=47"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=47"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
http:\/\/icpc.upc.edu.cn\/problem.php?cid=1459&pid=3<\/a><\/p>\n
http:\/\/icpc.upc.edu.cn\/problem.php?cid=2510&pid=4<\/a><\/p>\n
http:\/\/icpc.upc.edu.cn\/problem.php?cid=1459&pid=2<\/a><\/p>\n