Pagini recente » Cod sursa (job #2945469) | Cod sursa (job #720125) | Cod sursa (job #2174441) | Cod sursa (job #2357708) | Cod sursa (job #1898415)
#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 );
t[0]=-1;
t[1]=0;
int cnt=0, p=2;
while(p<=m){
if(w[cnt]==w[p-1]){
cnt++;
t[p]=t[p-1]+1;
p++;
}
else if(cnt>0){
cnt = t[cnt];
}
else{
t[p]=0;
p++;
}
}
vector<int> sols;
int i=0;
p=0;
while(p+i <= n){
if(i==m){
nrsol++;
sols.push_back(p);
if(nrsol == 1000)
goto Done;
p=p+i-t[i];
i=t[i];
}
if(s[p+i]==w[i])
{
i++;
}
else if(i==0){
p++;
}
else{
p=p+i-t[i];
i=t[i];
}
}
Done:
cout<<nrsol<<"\n";
for(int i=0; i<nrsol; i++)
cout<<sols[i]<<" ";
return 0;
}