Pagini recente » Cod sursa (job #1701121) | Cod sursa (job #2935212) | Cod sursa (job #1989255) | Cod sursa (job #1051682) | Cod sursa (job #2977727)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
#define MAX 2000005
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char pat[MAX],txt[MAX];
int poz[1024],pi[MAX];
int txt_l,pat_l;
int poz_k;
int main() {
in.getline(pat,MAX);
in.getline(txt,MAX);
txt_l=strlen(txt);
pat_l=strlen(pat);
if(txt_l<pat_l){
out<<0;
return 0;
}
int j=0;
for(int i=1;i<pat_l;i++){
while(j and pat[i]!=pat[j])
j=pi[j-1];
if(pat[i]==pat[j])
j++;
pi[i]=j;
}
for(int i=0;i<txt_l;i++){
while(j and pat[j]!=txt[i])
j=pi[j-1];
if(pat[j]==txt[i])
j++;
if(j==pat_l){
if(poz_k<1001)
poz[poz_k++]=i-j+1;
j=pi[j-1];
}
}
out<<poz_k<<"\n";
for(int i=0;i<min(poz_k,1000);i++){
out<<poz[i]<<" ";
}
out<<"\n";
return 0;
}