Pagini recente » Cod sursa (job #2349734) | Cod sursa (job #1236215) | Cod sursa (job #1052042) | Cod sursa (job #1274317) | Cod sursa (job #3305275)
#include <cstring>
#include <fstream>
#define MOD 100007
#define MOD2 100021
using namespace std;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001], b[2000001];
int aa2 = 0,a2 = 0, nr = 0;
int v[200001], nv = 0;
fin>>a>>b;
int na = strlen(a);
for(int i=0;i<na;i++)
{
int resta = a[i] - 'A';
a2 = (a2 * 26 + resta) % MOD;
aa2 = (aa2 * 26 + resta) % MOD2;
}
int nb = strlen(b);
int b2 = 0, bb2 = 0;
for(int i=0; i<na; i++)
{
int r = b[i] - 'A';
b2 = (b2 * 26 + r) % MOD;
bb2 = (bb2 * 26 + r) % MOD2;
}
if(a2 == b2 && aa2 == bb2)
{
nr++;
v[nv++] = 0;
}
int p = 1;
for(int i=1;i<=na-1;i++)
p = (p * 26) % MOD;
int p2 = 1;
for(int i=1;i<=na-1;i++)
p2 = (p2 * 26) % MOD2;
for(int i=1; i<nb - na; i++)
{
int r1 = b[i-1] - 'A';
int r2 = b[i + na - 1] - 'A';
b2 = ((b2 - (r1 * p) % MOD + MOD) * 26 + r2) % MOD;
bb2 = ((bb2 - (r1 * p2) % MOD2 + MOD2) * 26 + r2) % MOD2;
if(a2 == b2 && aa2 == bb2)
{
nr++;
v[nv++] = i;
}
}
fout<<nr<<"\n";
for(int i=0; i<min(nv, 1000); i++)
fout<<v[i]<<" ";
return 0;
}