Pagini recente » Cod sursa (job #2703018) | Cod sursa (job #709689) | Cod sursa (job #2821600) | Cod sursa (job #1587651) | Cod sursa (job #2977721)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define MAX 2000005
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char pat[MAX],txt[MAX];
int poz[1020];
int txt_l,pat_l;
int poz_k;
vector<int> pi;
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;
pi[0]=0;
for(int i=1;i<pat_l;i++){
while(j and pat[i]!=pat[j])
j=pat[j-1];
if(pat[i]==pat[j])
j++;
pat[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){
j=pi[j-1];
if(poz_k<1001)
poz[poz_k++]=i-j+1;
}
}
out<<poz_k;
for(int i=0;i<min(poz_k,1000);i++){
out<<poz[i]<<" ";
}
out<<endl;
return 0;
}