KMP

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
char s[M],p[N];
int ne[M];
int main()
{
    int n,m;
    cin>>n>>p + 1>>m>>s + 1;
    
    for(int i = 2, j = 0; i <= n; i ++)
    {
        while(j && p[i] != p[j + 1])j = ne[j];
        if(p[i] == p[j + 1])j ++;
        ne[i] = j; 
    }
    
    
    for(int i = 1, j = 0; i <= m; i ++)
    {
        while(j && s[i] != p[j + 1])j = ne[j];
        if(s[i] == p[j + 1])j ++;
        if(j == n)
        {
            cout<<i - n<<' ';
            j = ne[j];
        }
    }
    
    
}

ne[j]存的是对于模板串p,当前最大后缀与前缀相等的长度,有了这个长度,可以在s[i] != p[j + 1]时,让p串前面保留的信息尽量的多



推荐下标从1开始写,因为这样ne数组里面

存的长度就是下次返回的下标


strstr(s, p)库函数(必须是char[])

若

s

中有

p

则返回第一次出现的

地址

,否则返回

NULL


char str[100] = "abcdefg";
char p[100] = "deq";
if(strstr(str,p))
{
	int pos = strstr(str, p ) - str;
	cout<<pos<<endl;
}

string 里面的 find()函数

存在返回

位置

,不存在返回

s.npos


	string s = "abcdefg";
	string p = "bcd";
	if(s.find(p) != s.npos)
	{
		int pos = s.find(p);
		cout<<pos<<endl;
	}
	else cout<<"no";