Pagini recente » Cod sursa (job #2551105) | Cod sursa (job #3195284) | Borderou de evaluare (job #2068980) | Cod sursa (job #2518669) | Cod sursa (job #2525710)
#include <bits/stdc++.h>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
int hashA1,hashA2,P1,P2;
char match[MAXN];
void Read()
{
f>>A;
f>>B;
f.close();
}
void Solve()
{
int lenA,lenB;
lenA = A.length();
lenB = B.length();
P1 = P2 = 1;
hashA1 = hashA2 = 0;
for(int i=0;i<lenA;++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(lenA > lenB)
{
g<<0<<'\n';
g.close();
return;
}
int hash1 = 0;
int hash2 = 0;
for(int i=0;i<lenA;++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=lenA;i<lenB;++i)
{
hash1 = ((hash1-(B[i-lenA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
hash2 = ((hash2 - (B[i-lenA]*P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
if(hash1 == hashA1 && hash2 == hashA2)
{
match[i-lenA+1] = 1;
++Nr;
}
}
g<<Nr<<'\n';
Nr = 0;
for(int i=0;i<lenB && Nr< 1000;++i)
if(match[i])
{
++Nr;
g<<i<<" ";
}
g<<'\n';
g.close();
}
int main()
{
Read();
Solve();
return 0;
}