Pagini recente » Cod sursa (job #509491) | Cod sursa (job #574597) | Cod sursa (job #2506838) | Cod sursa (job #1023128) | Cod sursa (job #2977767)
#include<bits/stdc++.h>
using namespace std;
#define MAX 2000005
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char pat[MAX],txt[MAX];
int pi[MAX];
int txt_l,pat_l;
vector<int> poz;
void build_pi(){
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;
}
}
void show(){
int l=poz.size();
out<<l<<"\n";
for(int i=0;i<min(l,1000);i++){
out<<poz[i]<<" ";
}
out<<"\n";
}
int main() {
in.getline(pat,MAX);
in.getline(txt,MAX);
txt_l=(int) strlen(txt);
pat_l=(int) strlen(pat);
if(txt_l<pat_l){
out<<0;
return 0;
}
build_pi();
int j=0;
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.push_back(i-pat_l+1);
j=pi[j-1];
}
}
show();
return 0;
}