4/23 18届浙江省赛

--------------------省赛入口------------------------

String Freshman

对于子串T，去匹配S的时候，若出现字母被重复利用，那么匹配S得到的答案肯定是错的； 只有当子串T的字母都不和首字母相同时，匹配主串时才能相同。 另一种思路： 用kmp算法求子串的最长公共前后缀。

#include 

using namespace std;
int m,p[100005];
char s[100005];
void pre()
{
    p[1]=0;int j=0;
    for(int i=1;i0&&s[j+1]!=s[i+1])
            j=p[j];
        if(s[i+1]==s[j+1])
            j++;
        p[i+1]=j;
    }
}
int main()
{
    cin>>m;
    cin>>(s+1);
    pre();
    int flag=0;
    for(int i=1;i