Pagini recente » Cod sursa (job #2393342) | Cod sursa (job #866817) | Cod sursa (job #2041383) | g6c2h7e4f5c2h7b1c2 | Cod sursa (job #2785500)
#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++; rez.push(i-p+1); p = v_prefix[p] + 1;}
}else{
p = v_prefix[subsir[p]];
}
}
fout << cnt << '\n';
while(!rez.empty()) {cout << rez.front() << " "; rez.pop();}
return 0;
}