以下是我今天解题的题解报告：
[1] 求解next数组
题目描述：
在求解KMP过程中，会先求解next数组，给定一个字符（长度不超过40），输出对应next数组
具体描述：
给定一个字符串t，如 abcdabc，把从第一个字符开始的t的子串称为t的前缀，如a,ab,abc,abcd…
给定一个字符串t，如 abcdabc，把从某一个字符开始到最后一个字符的t子串称为t的后缀，如c,bc,abc,dabc,cdabc…
求出t的子串对应的 前缀长度等于后缀长度 的值 及 next数组。
如 a ab abc abcd abcda abcdab abcdabc
0 0 0 0 1 2 3
前缀子串和后缀子串：对模式P以及某个位置j，存在最大的k值，使得：p0p1…pk = pj-kpj-k+1…pj。(注意k不能等于j，否则等式左右两边是同一个字符串)。
输入
一个字符串
输出
对应的next数组。
样例输入
abcabceabcabca
样例输出
00012301234564
题目类型：
模拟，BFS，拓扑排序
思路：
Kmp算法中的关键,求解next数组,
参考博客: https://www.cnblogs.com/tangzhengyue/p/4315393.html


#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
#define ll long long
#define N 45 
using namespace std;
 
int main()
{
    char a[N];
    int next[N];
    int s,i,j=-1;
    scanf("%s",a+1);
    int len = strlen(a+1);
     
    for(int i = 2 ; i <= len ; i++){
        while(j && a[j+1] != a[i]){
            j=next[j];
        }
        if(a[j+1]==a[i]){
            j++;
        }
        next[i]=j;
    }
    for(int i = 1; i <= len ; i++)
    cout<<next[i];
    return 0;
}

[2] Number Sequence
题目描述：
Given two sequences of numbers : a[1], a[2], … , a[N], and b[1], b[2], … , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], … , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.
输入
The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], … , a[N]. The third line contains M integers which indicate b[1], b[2], … , b[M]. All integers are in the range of [-1000000, 1000000].
输出
For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.
样例输入
2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1
样例输出
6
-1
思路:用kmp算法查找出现字串的最小下标,如果没有就输出-1,


#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
#define ll long long
//#define N 45 
using namespace std;
int nxt[1000005], s[10005], p[1000005];
int slen,plen; 
void getnnxt() 
{
    nxt[0] = -1;
    int k = -1;
    for (int i = 1; i <= slen - 1; i++)
    {
        while (k>-1 && s[k + 1] != s[i])k = nxt[k];
        if (s[k + 1] == s[i])k++;
        nxt[i] = k;
    }
}
int kmp()
{
    int k = -1;
    for (int i = 0; i <= plen - 1; i++)
    {
        while (k>-1 && s[k + 1] != p[i])k = nxt[k];
        if (s[k + 1] == p[i])k++;
        if (k == slen - 1)return i - slen + 2;
    }
    return -1;
}
int main()
{
    int t, n, m;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        slen = m;
        plen = n;
        for (int i = 0; i<n; i++)cin >> p[i];
        for (int i = 0; i<m; i++)cin >> s[i];
        getnnxt();
        cout << kmp() << endl;
    }
    return 0;
}
 
//2
//13 5
//1 2 1 2 3 1 2 3 1 3 2 1 2
//1 2 3 1 3
//13 5
//1 2 1 2 3 1 2 3 1 3 2 1 2
//1 2 3 2 1

[3] Power Strings
题目描述：
Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “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).
输入
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.
输出
For each s you should print the largest n such that s = a^n for some string a.
样例输入
abcd
aaaa
ababab
.
样例输出
1
4
3
思路:翻译过来意思就是求最短的循环的字串长度的循环次数,如果不存在符合要求的字串就以字符串S为字串,循环次数就是1,
定理：假设字符串S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]]
证明：
设S=q1q2q3q4q5q6q7q8，并设next[8] = 6，此时str = S[len - next[len]] = q1q2，由字符串特征向量next的定义可知，q1q2q3q4q5q6 = q3q4q5q6q7q8，即有q1q2＝q3q4，q3q4＝q5q6，q5q6＝q7q8，即q1q2为循环子串，且易知为最短循环子串。由以上过程可知，若len可以被len - next[len]整除，则S存在循环子串，否则不存在。
解法：利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])，否则为1。

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int len,nex[1000005];
char s[1000005];
void getnex()
{
    int j=-1;
    for (int i=0;i<len;i++)
    {
        while(j!=-1 && s[j+1]!=s[i]) j=nex[j];
        if (s[j+1]==s[i] && i!=0) j++;
        nex[i]=j;
    }
}
int main()
{
    while(~scanf("%s",s))
    {
        if (s[0]=='.') return 0;
        len=strlen(s);
        getnex();
        if (len%(len-nex[len-1]-1)==0&&len!=nex[len-1]+1)
        printf("%d\n",len/(len-nex[len-1]-1));
        else
        printf("1\n");
    }
    return 0;
}