Pagini recente » Cod sursa (job #2858102) | Cod sursa (job #719633) | Cod sursa (job #1617933) | Cod sursa (job #350117) | Cod sursa (job #1895250)
#include<bits/stdc++.h>
#define N 2000020
using namespace std;
int p[N], rs[N];
int main(){
string a, b;
int n, m, k=0;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>b>>a;
n=a.length();
m=b.length();
p[0]=0;
int len=0, i=1, j, q=0;
for (i = 2, p[1] = 0; i <= m; ++i)
{
while (q && b[q+1] != b[i])
q = p[q];
if (b[q+1] == b[i])
++q;
p[i] = q;
}
/* while(i<m){
if(b[len]==b[i]){
len++;
p[i]=len;
i++;
}else{
if(len == 0){
p[i]=0;
i++;
}else{
len=p[len-1];
}
}
}*/
i=0;
j=0;
while(i<n){
if(a[i]==b[j]){
i++;
j++;
}
if(j==m){
rs[++k]=i-j;
j=p[j-1];
}
else if(i<n && a[i]!=b[j]){
if(j!=0){
j=p[j-1];
}else{
i++;
}
}
}
g<<k<<endl;
for(i=1;i<=k;i++) g<<rs[i]<<' ';
return 0;
}