Pagini recente » Monitorul de evaluare | Istoria paginii runda/andrei_15/clasament | Rating Balan Petru (Malik5547) | Cod sursa (job #1325154) | Cod sursa (job #2573096)
#include<bits/stdc++.h>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
char A[MAXN], B[MAXN];
int NA, NB;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int hashA1, hashA2, P1, P2;
char match[MAXN];
int main()
{
fin.getline(A,MAXN);
fin.getline(B,MAXN);
int NA = strlen(A);
int NB = strlen(B);
P1 = P2 = 1;
hashA1 = hashA2 = 0;
for(int i=0;i<NA;i++)
{
hashA1 = (hashA1 * P + A[i]) % MOD1;
hashA2 = (hashA2 * P + A[i]) % MOD2;
if(i!=0)
{
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
}
if(NA > NB)
{
fout<<'0\n';
}
else
{
int hash1 = 0;
int hash2 = 0;
for(int i=0;i<NA;i++)
{
hash1 = (hash1 * P + B[i]) % MOD1;
hash2 = (hash2 * P + B[i]) % MOD2;
}
int Nr = 0;
if(hash1 == hashA1 && hash2 == hashA2)
{
match[0] = 1;
Nr++;
}
for(int i = NA;i<NB;i++)
{
hash1 = ( ( (hash1 - B[i-NA]*P1) % MOD1 + MOD1 ) * P + B[i]) % MOD1;
hash2 = ( ( (hash2 - B[i-NA]*P2) % MOD2 + MOD2 ) * P + B[i]) % MOD2;
if(hash1 == hashA1 && hash2 == hashA2)
{
match[i-NA+1] = 1;
Nr++;
}
}
fout<<Nr<<'\n';
Nr = 0;
for(int i=0;i<NB && Nr<1001;i++)
{
if(match[i])
fout<<i<<" ",Nr++;
}
}
return 0;
}