Pagini recente » Cod sursa (job #1584564) | Monitorul de evaluare | Cod sursa (job #3040981) | Cod sursa (job #2952092) | Cod sursa (job #1180846)
#include<fstream>
#include<string>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string s,t;
int a[20000020],k=0,sol[10000000];
int main(){
fi>>t>>s;
for(int i=t.size();i;i--)t[i]=t[i-1];//t[0]=' ';
for(int i=s.size();i;i--)s[i]=s[i-1];//s[0]=' ';
int q=0;
a[0]=-1; a[1]=0;
/* for (int i=2; i<=t.size(); ++i){
q=i-1;
while (q>0&&t[a[q]+1]!=t[i]) q=a[q];
a[i]=a[q]+1;
}*/
for(int i=2;i<=t.size();i++){
while(q && t[q+1]!=t[i])q=a[q];
if(t[q+1]==t[i])q++;
a[i]=q;
// fo<<a[i]<<" ";
}
// fo<<endl;
q=0;
for(int i=1;i<=s.size();i++){
while(q && t[q+1]!=s[i])q=a[q];
if(t[q+1]==s[i])q++;
if(q==t.size()){
sol[++k]=i-q;
q=a[q];
}
}
fo<<k<<endl;
for(int i=1;i<=k && i<=1000;i++)fo<<sol[i]<<" ";
// fo<<endl;
}