Pagini recente » Cod sursa (job #2722802) | Cod sursa (job #2055494) | Cod sursa (job #949765) | Cod sursa (job #1678482) | Cod sursa (job #1997405)
#include <iostream>
#include <fstream>
#include <cstring>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
#define NMAX 1000
#define LMAX 2000000
using namespace std;
void PrefixTable(char pattern[],int Pi[]){
int m=strlen(pattern);
int k=0;
Pi[0]=0;
for(int i=1;i<m;i++){
while(k>0&&pattern[i]!=pattern[k])
k=Pi[k-1];
if(pattern[k]==pattern[i])
k++;
Pi[i]=k;
}
}
void KMP(char pattern[],char text[],int Pi[],int&num,int Rasp[]){
int m=strlen(pattern);
int n=strlen(text);
int k=0;
num=0;
for(int i=0;i<n;i++){
while(pattern[k]!=text[i]&&k>0)
k=Pi[k];
if(pattern[k]==text[i])
{
k++;
}
if(k==m){
Rasp[++num]=i-k+1;
k=Pi[k-1];
}
}
}
char patt[LMAX+2];
char text[LMAX+2];
ifstream in(INFILE);
ofstream out(OUTFILE);
int Pi[LMAX+2];
int Rasp[NMAX+2];
int NUM;
int main()
{
in.getline(patt,LMAX+1);
in.getline(text,LMAX+1);
PrefixTable(patt,Pi);
KMP(patt,text,Pi,NUM,Rasp);
if(NUM>NMAX)
NUM=NMAX;
out<<NUM<<"\n";
for(int i=1;i<=NUM;i++){
out<<Rasp[i]<<" ";
}
return 0;
}