KMP的初步认识及题目分析

KMP算法对于像我这样的ACM菜鸡来说实在难以理解

虽然有大佬讲课，但是还是不理解

感谢下面这位大犇的博客，让我看懂了KMP（跪谢）

https://www.cnblogs.com/SYCstudio/p/7194315.html

---------------------------------------------------------------------------------------------------------------------------

下面是我对于学校题目的一些总结

KMP模板（解释太麻烦了，看上面的大佬博客就行）

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
int tnext[1000010];

void get_next(string ptr)
{
    tnext[0] = -1;
    int len = ptr.size();
    int j;
    for (int i = 1; i <len; i++)
    {
        int j = tnext[i - 1];
        while (j>=0&&ptr[i] != ptr[j+1])
        {
            j = tnext[j];
        }
        if (ptr[i] == ptr[j+1]) j++;
        tnext[i] = j;
       // cout << tnext[i] << endl;
    }

}
void KMP(string str, string ptr)
{
    get_next(ptr);
    for (int i = 0, j = -1; i < str.size(); i++)
    {
        while (j >= 0 && (j == str.size() - 1 || str[i] != ptr[j+1]))
        {
            j = tnext[j];
        }
        if (str[i] == ptr[j + 1]) j++;
        if (j == ptr.size() - 1) cout << i - j << endl;
    }

}
int main()
{
    string str, ptr;//str是长串，ptr是短串即目标串，要在str中去找ptr
    cin >> str >> ptr;
    KMP(str,ptr);
    return 0;
}

---------------------------------------------------------------------------------------------------------------------------

HDU-4763-Theme Section

http://acm.hdu.edu.cn/showproblem.php?pid=4763

本题大意就是要求找出一串字符串的border，且该border在中间出现过

思路是先算next数组，如果next数组在全长的情况下不是-1，那么就进一步去字符串里找border

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
using namespace std;
int tnext[1000010];

void get_next(string ptr)
{
    tnext[0] = -1;
    int len = ptr.size();
    int j;
    for (int i = 1; i < len; i++)
    {
        int j = tnext[i - 1];
        while (j >= 0 && ptr[i] != ptr[j + 1])
        {
            j = tnext[j];
        }
        if (ptr[i] == ptr[j + 1]) j++;
        tnext[i] = j;
        // cout << tnext[i] << endl;
    }

}
bool cc;
void KMP(string str, string ptr)
{
    get_next(ptr);
    for (int i = 0, j = -1; i < str.size(); i++)
    {
        while (j >= 0 && (j == str.size() - 1 || str[i] != ptr[j + 1]))
        {
            j = tnext[j];
        }
        if (str[i] == ptr[j + 1]) j++;
        if (j == ptr.size() - 1)
        {
            if (i - j != 0 && i - j != str.size() - ptr.size() + 1) cc = true;
        }
    }

}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        string str;
        cin >> str;
        cc = false;
        memset(tnext, 0, sizeof(tnext));
        get_next(str);
        int k = tnext[str.size() - 1];
        while (2 * (k + 1) + 1 > str.size()) k = tnext[k];//前缀和后缀不能接壤
        if (k == -1) cout << "0" << endl;
        else
        {
            while (k != -1)//先是从满足条件的最大border开始判断，不行的话用小一点的border，直到没有
            {
                string ptr(str, 0, k + 1);//截取border

                KMP(str, ptr);
                if (cc) {//找到了满足中间出现border条件的
                    cout << k + 1 << endl; break;
                }
                else k = tnext[k];//没找到就看下一层border
            }
            if(!cc) cout << 0 << endl;
        }
    }
    return 0;

}

---------------------------------------------------------------------------------------------------------------------------

HDU-3336-Count the string

 http://acm.hdu.edu.cn/showproblem.php?pid=3336

题目大意就是找出一个字符串的所有前缀在字符串里出现过几次

思路是：由于每个前缀自身都会出现一次，如果一个字符串长度为n，那么总共有n个前缀，所以前缀至少出现n次

之后任务就变成了前缀在其之后出现了几次

而next数组的含义是字符串长度为k时，其border的长度，如果我们遍历next数组求和，就可以达到有多少个前缀出现在了后面

#include <iostream>
#include <cstring>
#include<string>
using namespace std;
int pos[1000100];
int num = 0;
void get_next(string ptr)
{
    pos[0] = -1;
    
    for (long long int i = 1,j=-1; i < ptr.size(); i++)
    {
        
        while (j >= 0 && ptr[i] != ptr[j + 1]) j = pos[j];
        if (ptr[i] == ptr[j + 1]) j++;
        pos[i] = j;
       
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long int t;
    cin >> t;
    while (t--)
    {
        long long int size;
        string str;
        cin >> size;
        cin >> str;
        num = 0;
        get_next(str);
        for (int i = 1; i < size; i++)
        {
            if (pos[i] != -1) num++;
            num %= 10007;
        }
       
       cout << (num+size)%10007 << endl;
    }
}

---------------------------------------------------------------------------------------------------------------------------

HDU-1358-Period

http://acm.hdu.edu.cn/showproblem.php?pid=1358

题目大意：有一串字符串，找出他的长度为多少时，是由循环节组成的

解题思路：遍历总长度，算出每个长度对应的next数组，那么周期就是len-next[k]，如果长度%周期==0

说明它是由整数个周期组成的，输出长度/周期即可

#include <iostream>
#include<string>
using namespace std;
int pos[1000100];
void get_pos(string str)
{
    pos[0] = -1;
    for (int i = 1; i < str.size(); i++)
    {
        int j = pos[i - 1];
        while (j >= 0 && str[i] != str[j + 1]) j = pos[j];
        if (str[i] == str[j + 1]) j++;
        pos[i] = j;
    }
}
int main()
{
    int n,num=0;
    while (cin >> n && n)
    {
        num++;
        //if (num != 1) cout << endl;
        string str;
        cin >> str;
        
       
        cout << "Test case #" << num << endl;
        get_pos(str);
        for (int i = 2; i <= str.size(); i++)
        {
            if (pos[i-1]!=-1&&(i % (i - pos[i - 1] - 1) == 0))//存在border是前提
            {
                cout << i << " " << i / (i - pos[i - 1] - 1) << endl;
            }
        }
        cout << endl;
    }
}

---------------------------------------------------------------------------------------------------------------------------

HDU-3746-Cyclic Nacklace

http://acm.hdu.edu.cn/showproblem.php?pid=3746

题目大意：给出一字符串，要求问要补多少个字符才能凑出一个循环节构成的字符串

思路：算出next数组，然后找出周期，周期-（长度%周期）就是需要补充的数量

考虑到已经是循环节构成的字符串要输出0，没有border的要输出自身长度

（此题cin，memset好像不能用，题目有问题）

#include <iostream>
#include<string>
#include<cstring>
#include<stdio.h>
using namespace std;
int pos[100010];
char str[100010];
int main()
{

    int n;
    scanf("%d", &n);
    getchar();
    while (n--)
    {
        gets(str);
        pos[0] = -1;
        int len = strlen(str);
        for (int i = 1; i < len; i++)
        {
            int j = pos[i - 1];
            while (j >= 0 && str[i] != str[j + 1]) j = pos[j];
            if (str[i] == str[j + 1])j++;
            pos[i] = j;
        }

        int cyl = len - (pos[len - 1] + 1);
        int t = (cyl - (len % cyl)) % cyl;
        if (t == 0 && len / cyl == 1) t += len;
        
        printf("%d
", t);
    }
}