KMP算法

   int n, m;
  cin >> n >> a + 1 >> m >> b + 1;
这两行代码的意思是输入字符串a，b但是是从下标1开始输入的

可以按照此方式输入字符串，但是输出必须按照下标for循环输出，不能直接输出

 1 #include<iostream>
 2 using namespace std;
 3 const int N = 100010;
 4 const int M = 1000010;
 5 char a[N], b[M];
 6 int ne[N];
 7 int main()
 8 {
 9     int n, m;
10     cin >> n >> a + 1 >> m >> b + 1;
11 
12 //给next数组进行编号
13     for (int i = 2, j = 0; i <= n; i++)
14     {
15         while (j && a[i] != a[j + 1])j = ne[j];
16         if (a[i] == a[j + 1])j++;
17         ne[i] = j;
18     }
19 //进行判断，验证利用next数组遍历
20     for (int i = 1, j = 0; i <= m; i++)
21     {
22         while (j && b[i] != a[j + 1])j = ne[j];
23         if (b[i] == a[j + 1])j++;
24         if (j == n)
25         {
26             printf("%d ", i - n);
27             j = ne[j];
28         }
29     }
30     return 0;
31 }

Trie树

主要用于高效的存储和查找字符串

#include<iostream>
using namespace std;
const int N = 100010;
int a[N][26]; int idx;
int num[N];
void insert(char str[])
{
    int p = 0;//一开始的层数
    for (int i = 0; str[i]; i++)
    {
        int x = str[i] - 'a';
        if (!a[p][x]) a[p][x] = ++idx;如果没有就创建，但是存的位置赋予独一无二的值idx，和数组模拟链表类似
        p = a[p][x];//p走到下一个节点
    }
    num[p]++;//因为p最终到达地方唯一所以存入
}

int find(char str[])
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int x = str[i] - 'a';
        if (!a[p][x]) return 0;
        p = a[p][x];
    }
    return num[p];//最后返回个数
}

int main()
{
    int n; cin >> n;
    while (n--)
    {
        char c; cin >> c; char str[N];
        if (c == 'I')
        {
            cin >> str;
            insert(str);
        }
        else {
            cin >> str;
            cout << find(str) << endl;
        }
    }
    return 0;
}

526互联

KMP算法 Trie树（9/9）

KMP算法

Trie树