Pagini recente » Cod sursa (job #277383) | Cod sursa (job #2514478) | Cod sursa (job #1639310) | Clasamentul arhivei de probleme | Cod sursa (job #1216275)
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
typedef unsigned int uint;
uint fail[2000000 + 5],n,m,poz[1001];
char p[2000000 + 10],w[2000000 + 10];
inline void failure(){
uint i = 1,j = 0;
while(i < m){
if(p[i] == p[j]){
fail[i] = ++j;
i++;
}
else{
if(j != 0)
j = fail[j - 1];
else{
fail[i] = 0;
j = 0;
i++;
}
}
}
}
inline void kmp(){
uint i = 0,j = 0,c = 0;
for(i = 0; i < n; ){
if(w[i] == p[j]){
j++;
i++;
}
else{
if(j != 0)
j = fail[j - 1];
else{
j = 0;
i++;
}
}
if(j == m){
if(c < 1000)
poz[c] = i - j;
c++;
i = i - j + 1;
j = 0;
}
}
printf("%d\n",c);
uint max = c >= 1000 ? 1000 : c;
for(i = 0; i < max; i++)
printf("%d ", poz[i]);
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(p,sizeof(p),stdin);
fgets(w,sizeof(w),stdin);
for(; p[m] > 0; m++);
m--;
for(; w[n] > 0; n++);
failure();
kmp();
return 0;
}