主要是记录学习的过程，大多数引用它人博客，方便复习，毕竟时间不多，cpc也不是我的主业了

数据结构

1.kmp

求模式串在原串中出现的次数

详细解析链接

2.扩展kmp

扩展KMP求的是对于原串S1的每一个后缀子串与模式串S2的最长公共前缀

3.Karp-Rabin

求模式串在原串中出现的位置，时间复杂度O(m+n);其实就是把字符串hash化，用hash值代替字符串比较，用unsigned int代替int可以省略取模步骤，f_zyj模板似乎有点小问题，以下为修改后的

typedef unsigned int uint;
uint REHASH(uint a,uint b,uint h)
{
    return ((h-a)*2+b);
}
int krmatch(char *x, int m, char *y, int n)
{
    //search x in y
    uint d, hx, hy, i, j;
    for (d = i = 1; i < m; i++)
    {
        d = (d << 1);
    }
    for (hy = hx = i = 0; i < m; i++)
    {
        hx = ((hx << 1) + x[i]);
        hy = ((hy << 1) + y[i]);
    }
    printf("%u %u\n",hx,hy);
    for (j = 0; j <= n - m; j++)
    {
        if (hx == hy && memcmp(x, y + j, m) == 0)
        {
            return j;
        }
        hy = REHASH((uint)y[j]*d, (uint)y[j + m], (uint)hy);
        printf("%u %u\n",hx,hy);
    }
    return 0;   //理论上不会背执行，全部都应该从上一个return返回
}

int main()
{
    char a[1000];
    char b[1000];
    scanf("%s%s",a,b);
    printf("%d\n",krmatch(a,strlen(a),b,strlen(b)));
}

4.马拉车Manacher

求最长回文子串，预处理后每个位置的值是指以当前位置为中心的最长回文串的长度

5.strstr

这是c内置的函数，strstr(char *a, char *b) return p;函数返回一个指针，它指向字符串b第一次在字符串a中出现的位置，如果没有找到返回NULL，
据说效率堪比kmp

6.Sunday算法

与KMP，BM，Karp-Rabin一样，效率最高而已

7.AC自动机

给定n个模式串和1个文本串，求有多少个模式串在文本串中出现过

8.后缀数组