Pagini recente » Cod sursa (job #955072) | Cod sursa (job #178541) | Cod sursa (job #2106134) | Cod sursa (job #3208257) | Cod sursa (job #1997162)
#include <iostream>
#include <fstream>
#include <cstring>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define LMAX 2000000
#define NMAX 1000
using namespace std;
void CrPrefTable(char pat[],int n,int P[]){
P[0]=0;
int border=0;
for(int i=1;i<n;i++){
while(border>0&&pat[i]!=pat[border])
border=P[border-1];
if(pat[i]==pat[border])
border=border+1;
else{
P[i]=0;
border=0;
}
P[i]=border;
}
}
void KMP(char pat[],char text[],int Rasp[],int&num){
int m=strlen(pat);
int n=strlen(text);
int Pi[m+n+1];
char str[m+n+1];
for(int i=0;i<m;i++)
str[i]=pat[i];
str[m]='$';
for(int i=0;i<n;i++){
str[m+i+1]=text[i];
}
CrPrefTable(str,m+n+1,Pi);
num=0;
for(int i=m+1;i<m+n+1;i++){
if(Pi[i]==m){
Rasp[num++]=i-2*m;
}
}
}
ifstream in(INFILE);
ofstream out(OUTFILE);
char Pattern[LMAX];
char Text[LMAX];
int Rasp[LMAX];
int num;
int main()
{
in.getline(Pattern,LMAX);
in.getline(Text,LMAX);
KMP(Pattern,Text,Rasp,num);
if(num>NMAX)
num=NMAX;
out<<num<<"\n";
for(int i=0;i<num;i++){
out<<Rasp[i]<<" ";
}
return 0;
}