Pagini recente » Cod sursa (job #497724) | Cod sursa (job #3124159) | Cod sursa (job #1028139) | Cod sursa (job #1390671) | Cod sursa (job #2302813)
#include <cstdio>
#include <cstring>
#define MaxLength 2000005
using namespace std;
char Text[MaxLength], Pattern[MaxLength];
int LT, LP, i, j, pi[MaxLength], List[1005], N; bool k;
int main()
{
freopen("KMP.in", "r", stdin);
freopen("KMP.out", "w", stdout);
fgets(Pattern, 101, stdin);
fgets(Text, 101, stdin);
LT=strlen(Text); LP=strlen(Pattern);
if(Pattern[LP-1]=='\n') --LP;
if(Text[LT-1]=='\n') --LT;
for(i=1; i<LP; ++i) if(Pattern[pi[i-1]]==Pattern[i])pi[i]=pi[i-1]+1;
for(i=0; i<LT; ++i){
if(Text[i]==Pattern[0]){
k=true;
for(j=0; j<LP; ++j && ++i)
if(Text[i]!=Pattern[j]) {i=i-pi[j-1]-1; k=false; break;}
if(k==true){
--i; ++N;
if(N<=1000) List[N]=i-LP+1;
i-=pi[LP-1];
}
}
}
printf("%d\n", N);
for(i=1; i<=N && i<=1000; ++i)printf("%d ", List[i]);
return 0;
}