Pagini recente » Cod sursa (job #1582432) | Cod sursa (job #2392736) | Cod sursa (job #142804) | Cod sursa (job #291027) | Cod sursa (job #2785563)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char subsir[2000005], sir[2000005];
int prefix_vector[2000005], rez[2000005];
int l_subsir, l_sir, cnt;
void construire_vector_prefix(char subsir[]){
prefix_vector[0] = -1;
prefix_vector[1] = 0 ;
int nr_caractere_repetate = 0;
for(int i=2; i<=l_subsir; i++){
if(subsir[i] == subsir[nr_caractere_repetate + 1]){
nr_caractere_repetate++;
}else nr_caractere_repetate = 0;
prefix_vector[i] = nr_caractere_repetate;
}
}
int main(){
fin >> subsir >> sir ;
l_subsir = strlen(subsir), l_sir = strlen(sir);
for(int i = l_subsir; i>=1; i--){
subsir[i] = subsir[i-1];
}
for(int i = l_sir; i>=1; i--){
sir[i] = sir[i-1];
}
construire_vector_prefix(subsir);
int p = 0;
for(int i=1; i<=l_sir; i++){
while (p && subsir[p+1] != sir[i])
p = prefix_vector[p];
if (subsir[p+1] == sir[i])
++p;
if (p == l_subsir)
{
p = prefix_vector[p];
++cnt;
if (cnt <= 1000){
rez[cnt] = i-l_subsir;
}
}
}
fout << cnt << '\n';
if(cnt > 1000) cnt = 1000;
for(int i=1; i<=cnt; i++){
fout << rez[i] << ' ';
}
return 0;
}