Pagini recente » Cod sursa (job #2457311) | Cod sursa (job #703337) | Cod sursa (job #2109797) | Cod sursa (job #222178) | Cod sursa (job #1727792)
#include <bits/stdc++.h>
using namespace std;
const int BIG = 2000005;
char sir_total[BIG],sir_comparat[BIG],KMP[BIG];
int main() {
int n,m,k=0,cnt=0,j,index = 0;
int poz[BIG],z=0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s",sir_comparat+1,sir_total+1);
n = strlen(sir_total+1);
m = strlen(sir_comparat+1);
if(n < m){
printf("%d\n",0);
fclose(stdin);
fclose(stdout);
}
for(int i=1;i<=n;){
if(sir_comparat[i] == sir_comparat[index]){
KMP[i] = index;
index++;
i++;}
else{
if(index)
index = KMP[index-1];
else{
KMP[i] = 0;
i++;
}
}
}
while(k < n){
if(j == m){
poz[z] = k-j;
z++;
j=0;
}
if(sir_total[k] == sir_comparat[j]){
k++;
j++;
}
else
if(j)
j = KMP[j-1];
else
k++;
}
// for(int i=1;i<=n;i++){
//
// if(sir_total[i] == sir_comparat[k]){
// poz[z] = i-1;
// k++;
// for(j=i+1;k<=m;j++,k++)
// if(sir_total[j] == sir_comparat[k])
// cnt++;
// if(cnt+1 == m)
// z++;
// cnt= 0;k=1;
// }
// }
printf("%d\n",z);
z = min(z, 1000);
for(int i=0;i<z;i++)
printf("%d ",poz[i]);
return 0;
}