Pagini recente » Cod sursa (job #2214184) | Istoria paginii runda/simulare_oji_ichc_12_03/clasament | Cod sursa (job #660531) | Cod sursa (job #1505290) | Cod sursa (job #2323914)
#include <bits/stdc++.h>
#define N 2000001
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int k[N],r[N];
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() && n<1000; ++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;
r[++n]=i-a.length()+1;
}
}
out<<n<<"\n";
for(i=1; i<=n; ++i)
out<<r[i]<<" ";
return 0;
}