Pagini recente » Cod sursa (job #466769) | Cod sursa (job #1306218) | Cod sursa (job #1430169) | Cod sursa (job #1736643) | Cod sursa (job #2785514)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char subsir[2000001], sir[2000001];
int v_prefix[2000001], cnt;
queue <int> rez;
void construire_vector_prefix(char subsir[]){
v_prefix[0] = 0;
int prefix = 0;
for(int i=1; i<strlen(subsir); i++){
if(subsir[i] == subsir[prefix]){
v_prefix[i] = v_prefix[i-1] + 1;
prefix++;
}else{
v_prefix[i] = 0;
prefix = 0;
}
}
}
int main(){
fin >> subsir >> sir;
construire_vector_prefix(subsir);
int p = 0;
for(int i=0; i<strlen(sir); i++){
if(sir[i] == subsir[p]){
p++;
if(p == strlen(subsir) && cnt < 1000) {cnt++; rez.push(i-p+1); p = v_prefix[p] + 1;}
}else {
p = v_prefix[p];
}
}
fout << cnt << '\n';
while(!rez.empty()) {fout << rez.front() << " "; rez.pop();}
return 0;
}