Pagini recente » Cod sursa (job #2199296) | Cod sursa (job #577794) | Cod sursa (job #1196822) | Cod sursa (job #2375113) | Cod sursa (job #626337)
Cod sursa(job #626337)
#include <stdio.h>
#include<string.h>
#define baza 73
#define mod1 100007
#define mod2 100021
#define maxN 2000000
char tipar[maxN], sir[maxN];
int hashT1, hashT2, hashS1, hashS2, lT, lS, baza1, baza2;
int potriviri[1000], nr;
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", tipar, sir);
lT = strlen(tipar);
lS = strlen(sir);
if(lT > lS) return 0;
baza1 = baza2 = 1;
for(int i = 0; i < lT; i++)
{
hashT1 = (hashT1*baza + tipar[i]) % mod1;
hashT2 = (hashT2*baza + tipar[i]) % mod2;
hashS1 = (hashS1*baza + sir[i]) % mod1;
hashS2 = (hashS2*baza + sir[i]) % mod2;
if(i!=0)
{
baza1 = (baza1 * baza) % mod1;
baza2 = (baza2 * baza) % mod2;
}
}
if(hashT1 == hashS1 && hashT2 == hashS2)
potriviri[nr++] = 0;
for(int i = lT; i < lS && nr < 1000; i++)
{
hashS1 = ((hashS1 - (sir[i - lT]*baza1)%mod1 + mod1)*baza + sir[i]) % mod1;
hashS2 = ((hashS2 - (sir[i - lT]*baza2)%mod2 + mod2)*baza + sir[i]) % mod2;
if(hashT1 == hashS1 && hashT2 == hashS2)
potriviri[nr++] = i - lT + 1;
}
printf("%d\n", nr);
for(int i = 0; i < nr; i++)
printf("%d ", potriviri[i]);
printf("\n");
return 0;
}