Pagini recente » Cod sursa (job #1743941) | Cod sursa (job #2425849) | Cod sursa (job #749751) | Cod sursa (job #65064) | Cod sursa (job #889648)
Cod sursa(job #889648)
#include <cstdio>
#include <cstring>
#define nMax 2000005
char Pattern[nMax], Text[nMax];
int lenText, lenPattern;
int Next[nMax];
int nSol;
int Sol[nMax];
int min(int x, int y){
if(x<y) return x;
return y;
}
void Read(){
scanf("%s %s", Pattern, Text);
}
void buildNext(){
int k=0;
for(int i=1; i<lenPattern; i++){
if(Pattern[k] == Pattern[i])
Next[i+1] = ++k;
else
Next[i+1] = k = 0;
}
}
void Solve(){
int k=0;
for(int i=0; i<lenText; i++){
if(Text[i] == Pattern[k])
k++;
else{
if(k==lenPattern)
Sol[++nSol] = i-- - k;
k = Next[k];
}
}
}
void Write(){
printf("%d\n", nSol);
for(int i=1; i<=min(nSol,1000); i++)
printf("%d ", Sol[i]);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
Read();
lenText = strlen(Text);
lenPattern = strlen(Pattern);
buildNext();
Solve();
Write();
return 0;
}