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; }