Pagini recente » Cod sursa (job #270936) | Cod sursa (job #1478069) | Cod sursa (job #2212047) | Cod sursa (job #3228097) | Cod sursa (job #2451272)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MOD1 = 100007;
const int MOD2 = 100021;
string a,b;
int hasha1,hasha2,hash1,hash2,sol[2000005],cnt;
int main()
{
in >> a >> b;
int P1,P2;
P1 = P2 = 1;
for (int i=0; i<a.length(); i++)
{
hasha1 = (hasha1*26 + a[i])%MOD1;
hasha2 = (hasha2*26 + a[i])%MOD2;
if (i != 0)
{
P1 = (P1 * 26) % MOD1,
P2 = (P2 * 26) % MOD2;
}
}
for (int i=0; i<a.length(); i++)
{
hash1 = (hash1*26 + b[i])%MOD1;
hash2 = (hash2*26 + b[i])%MOD2;
}
if (hash1 == hasha1 && hash2 == hasha2)
{
sol[0] = 0;
cnt++;
}
for (int i=a.length(); i<b.length(); i++)
{
hash1 = ((hash1 - (b[i-a.length()]*P1)%MOD1 + MOD1)*26 + b[i])%MOD1;
hash2 = ((hash2 - (b[i-a.length()]*P2)%MOD2 + MOD2)*26 + b[i])%MOD2;
if (hash1 == hasha1 && hash2 == hasha2)
{
sol[cnt] = i-a.length() + 1;
cnt++;
}
}
out << cnt << "\n";
cnt = min(cnt,1000);
for (int i=0; i<cnt; i++)
{
out << sol[i] << " ";
}
return 0;
}