Pagini recente » Cod sursa (job #1170921) | Cod sursa (job #2287538) | Cod sursa (job #5957) | Cod sursa (job #660581) | Cod sursa (job #2977714)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define ll long long
#define MAX 2000005
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char pat[MAX],txt[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;
}
vector<int> pi(0,pat_l+1);
int j=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;
}
vector<int> poz;
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){
poz[poz_k++]=i-pat_l+1;
j=pi[j-1];
if(poz_k>1000)
break;
}
}
out<<poz_k;
for(int i=0;i<poz_k;i++){
out<<poz[i]<<" ";
}
out<<endl;
return 0;
}