Pagini recente » Cod sursa (job #1055561) | Cod sursa (job #2312238) | Cod sursa (job #1565173) | Cod sursa (job #2858563) | Cod sursa (job #1124681)
#include <cstdio>
#include <cstring>
#include <vector>
#define nmax 2000005
#define mod1 666013
#define mod2 1000003
#define baza 73
using namespace std;
char sir1[nmax],sir2[nmax];
int l1,l2;
int h1a,h2a;
int h1b,h2b;
int bazapa=1,bazapb=1;
vector <int> r;
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",sir1,sir2);
l1 = strlen(sir1);
l2 = strlen(sir2);
h1a = sir1[0];
h1b = sir1[0];
h2a = sir2[0];
h2b = sir2[0];
for (int i=1;i<l1;i++) {
bazapa = (bazapa*baza)%mod1;
bazapb = (bazapb*baza)%mod2;
h1a = (h1a*baza + sir1[i])%mod1;
h1b = (h1b*baza + sir1[i])%mod2;
h2a = (h2a*baza + sir2[i])%mod1;
h2b = (h2b*baza + sir2[i])%mod2;
}
for (int i=l1;i<=l2;i++) {
if (h1a == h2a && h1b == h2b) r.push_back(i-l1);
h2a = (((h2a - (sir2[i-l1]) * bazapa)%mod1 + mod1) * baza + sir2[i])%mod1;
h2b = (((h2b - (sir2[i-l1]) * bazapb)%mod2 + mod2) * baza + sir2[i])%mod2;
}
printf("%d\n",r.size());
int nr = 1;
for (vector <int> :: iterator it = r.begin();nr <= 1000 && it != r.end();nr++,it++) printf("%d ",*it);
return 0;
}