Pagini recente » Cod sursa (job #618650) | Cod sursa (job #2830126) | Cod sursa (job #2958303) | Cod sursa (job #2696730) | Cod sursa (job #2191809)
#include<cstdio>
#include<cstring>
const int BASE = 80;
const long long MOD = 100007;
const int NMAX = 2000000;
long long hashPref[1 + NMAX];
long long powBase[1 + NMAX];
int sol[1 + NMAX];
char A[1 + NMAX];
char B[1 + NMAX];
int n;
int get_code(char c)
{
return c - 'A' + 1;
}
int hashuri(char *s)
{
int ans = 0;
while(s[0] != '\0')
{
ans = (ans * BASE + get_code(s[0])) % MOD;
s++;
}
return ans;
}
int hash_interval(int i, int j) {
return (hashPref[j] + 100000 * MOD - (hashPref[i - 1] * powBase[j - i + 1]) ) % MOD;
}
int main()
{
int lenA , lenB , hasha ,total = 0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(A); ///CE CAUT
gets(B); /// textul propriu-zis
lenB = strlen(B);
lenA = strlen(A);
hasha = hashuri(A);
n = lenB;
for (int i = 0; i < lenB; i++)
hashPref[i] = (hashPref[i - 1] * BASE + get_code(B[i])) % MOD;
powBase[0] = 1;
for(int i = 1; i <= n + 3; i ++)
powBase[i] = (powBase[i - 1] * BASE) % MOD;
for(int i = 0; i <= lenB - lenA ; i ++)
{
if(hash_interval(i , i + lenA - 1) == hasha % MOD)
sol[++total] = i;
}
printf("%d\n",total);
for(int i = 1; i <= total ; i ++)
printf("%d ",sol[i]);
hasha = hashuri(A);
}