Pagini recente » Cod sursa (job #1495598) | Cod sursa (job #1619344) | Cod sursa (job #1402652) | Cod sursa (job #2800046) | Cod sursa (job #1899170)
#include <iostream>
#include<string>
#include<string.h>
#include<vector>
#include<fstream>
#define cin f
#define cout g
/**/
using namespace std;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s, w;
cin>>w>>s;
int m=w.size();
int n=s.size();
int nrsol=0;
int *t= new int[m+3];
memset(t, 0, sizeof(int) *m );
// cerr<<"m"<<m<<"\n";
t[0]=-1;
t[1]=0;
int cnt=0, p=2;
while(p<m){
if(w[cnt]==w[p-1]){
cnt++;
t[p]=cnt;
p++;
}
else if(cnt>0){
cnt = t[cnt];
}
else{
t[p]=0;
p++;
}
}
/*
for(int i=0; i<=m; i++)
cerr<<t[i]<<" ";
cerr<<"\n";
*/
vector<int> sols;
int i=0;
p=0;
while(p+i < n){
if(s[p+i]==w[i])
{
if(i==m-1){
nrsol++;
sols.push_back(p);
p=p+i-t[i];
i=t[i];
}
else i++;
}
else if(i==0){
p++;
}
else{
p=p+i-t[i];
i=t[i];
}
}
cout<<sols.size()<<"\n";
for(int i=0; i<min(nrsol, 1000); i++)
cout<<sols[i]<<" ";
return 0;
}