Pagini recente » Cod sursa (job #940698) | Cod sursa (job #1450167) | Cod sursa (job #1876261) | Monitorul de evaluare | Cod sursa (job #3349060)
#include <fstream>
#include <cstring>
#include <vector>
#define nmax (int)(2e6+1)
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int lps[nmax];
string a,b;
vector<int>v;
void get_lps(string s){
int i=1,len=0;
while(s[i]!=0){
if(s[i]==s[len])
lps[i++]=++len;
else if(len!=0)
len=lps[len-1];
else
i++;
}
}
int kmp(){
int r=0,i=0,n=a.size();
for(int j=0;b[j]!=0;j++)
if(a[i]==b[j]){
i++;
if(i==n){
r++;
if(r<=1000)
v.push_back(j-n+1);
i=lps[i-1];
}
}else if(i!=0)
i=lps[i-1],j--;
return r;
}
signed main()
{
cin>>a>>b;
get_lps(a);
cout<<kmp()<<'\n';
for(auto i:v)
cout<<i<<" ";
return 0;
}