Pagini recente » Cod sursa (job #2447239) | Cod sursa (job #13585) | Cod sursa (job #665366) | Cod sursa (job #3273558) | Cod sursa (job #2323918)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int k[2000001],r[1001];
int main(){
int i,j=0,n=0;
string a,b;
in>>a>>b;
for(i=1; i<a.length(); ++i){
if(a[i]!=a[j])
while(a[i]!=a[j] && j)
j=k[j-1];
if(a[i]==a[j])
++j;
k[i]=j;
}
j=0;
for(i=0; i<b.length(); ++i){
if(b[i]!=a[j])
while(b[i]!=a[j] && j)
j=k[j-1];
if(b[i]==a[j])
++j;
if(j==a.length()){
--j;
while(b[i]!=a[j] && j)
j=k[j];
if(b[i]==a[j]) ++j;
++n;
if(n<=1000)
r[n]=i-a.length()+1;
}
}
out<<n<<"\n";
for(i=1; i<=min(n,1000); ++i)
out<<r[i]<<" ";
return 0;
}