Pagini recente » Cod sursa (job #657554) | Cod sursa (job #1314690) | Cod sursa (job #963573) | Cod sursa (job #1668027) | Cod sursa (job #2488851)
//#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
int z[4000005];
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string p,s,total="";
int l=0,r=0,len,l1;
cin>>p;
cin>>s;
total+=p;
total+='$';
total+=s;
len=total.size();
l1=p.size();
for(int i=1;i<len;i++){
if(i>r){
l=i;
r=i;
while(r<len and total[r]==total[r-l]){
r++;
}
z[i]=r-l;
r--;
}
else{
if(z[i-l]<r-i){
z[i]=z[i-l];
}
else{
l=i;
while(r<len and total[r]==total[r-l]){
r++;
}
z[i]=r-l;
r--;
}
}
}
//cout<<"0 ";
int cnt=0;
for(int i=1;i<len;i++){
if(z[i]==l1){
cnt++;
}
}
cout<<cnt<<"\n";
if(cnt>1000)
cnt=1000;
for(int i=1;i<len;i++){
if(z[i]==l1){
cout<<i-l1-1<<" ";
}
}
return 0;
}