Pagini recente » Cod sursa (job #2119026) | Cod sursa (job #2119028)
#include <cstdio>
#include <cstring>
using namespace std;
char sir1[2000005], sir2[2000005];
int nr[2000005];
void citire(){
fgets(sir1, 2000005, stdin);
sir1[strlen(sir1) - 1] = 0;
fgets(sir2, 2000005, stdin);
sir2[strlen(sir2) - 1] = 0;
}
void construireInitiala(){
int l = strlen(sir1);
int nr1 = 0;
for(int i = 1; i < l; i++){
if(sir1[i] == sir1[nr1]){
nr1++;
nr[i] = nr1;
}
else{
nr1 = nr[nr1 - 1];
if(sir1[i] == sir1[nr1]){
nr1++;
}
nr[i] = nr1;
}
}
}
int sol[2000005];
int nrSol = 0;
void solve(){
int l = strlen(sir2);
int ll = strlen(sir1);
int p = 0;
for(int i = 0; i < l; i++){
if(sir2[i] == sir1[p]){
p++;
if(p == ll){
sol[nrSol] = i + 1;
nrSol++;
p = nr[p - 1];
// i--;
}
}
else{
while(p > 0){
p = nr[p - 1];
if(sir2[i] == sir1[p]){
p++;
break;
}
}
}
}
if(p == ll){
sol[nrSol] = l;
nrSol++;
}
printf("%d\n", nrSol);
if(nrSol > 1000){
nrSol = 1000;
}
for(int i = 0; i < nrSol; i++){
printf("%d ", sol[i] - ll);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
construireInitiala();
solve();
return 0;
}
//aabaabaaa
//010123452