Pagini recente » Cod sursa (job #2288968) | Cod sursa (job #2306946) | Cod sursa (job #2779733) | Cod sursa (job #2389720) | Cod sursa (job #2289359)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define nmax 2000005
using namespace std;
FILE *fin,*fout;
char txt[nmax],pat[nmax],lps[nmax];
int poz[1001],counter;
void Pattern_Preprocessing(const char* a)
{
int a_length=strlen(a);
lps[0]=0;
int i=0,j=1;
while(j<a_length)
if(a[i]==a[j])
i++,lps[j]=i,j++;
else
{
if(i)
i=lps[i-1];
else
lps[j]=0,j++;
}
}
void KMP(const char *a, const char *b)
{
int m=strlen(a),n=strlen(b);
Pattern_Preprocessing(a);
int i=0,j=0;
while(i<n)
{
if(a[j]==b[i])
i++,j++;
if(j==m)
poz[++counter]=i-j,j=lps[j-1];
else if(i<n && a[j]!=b[i])
{
if(j)
j=lps[j-1];
else
i++;
}
}
}
int main()
{
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
fscanf(fin,"%s%s",&pat,&txt);
KMP(pat,txt);
fprintf(fout,"%d\n",counter);
for(int i=1;i<=counter;i++)
fprintf(fout,"%d ",poz[i]);
return 0;
}