Pagini recente » Cod sursa (job #2596975) | Cod sursa (job #31366) | Cod sursa (job #422586) | Cod sursa (job #322934) | Cod sursa (job #1954185)
#include <fstream>
#include <cstring>
#include <vector>
#define P 80
#define Mod1 100007
#define Mod2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000010];
char b[2000010];
int main()
{
vector<int> v;
fin>>a;
fin>>b;
int NA = strlen(a);
int NB = strlen(b);
if(NA > NB)
{
fout<<0<<'\n';
return 0;
}
int HashA1 = 0;
int HashA2 = 0;
int Pow1 = 1;
int Pow2 = 1;
for(int i=0;i<NA;i++)
{
HashA1 = (HashA1 * P + a[i]- '0') % Mod1;
HashA2 = (HashA2 * P + a[i]- '0') % Mod2;
if(i!=0)
{
Pow1 = Pow1 * P % Mod1;
Pow2 = Pow2 * P % Mod2;
}
}
int HashB1 = 0;
int HashB2 = 0;
for(int i=0;i<NA;i++)
{
HashB1 = (HashB1 * P + b[i]- '0') % Mod1;
HashB2 = (HashB2 * P + b[i]- '0') % Mod2;
}
if(HashA1 == HashB1 && HashA2 == HashB2)
v.push_back(1);
for(int i=NA;i<NB;i++)
{
HashB1 = (((HashB1 - Pow1 * (b[i-NA] - '0')) % Mod1 + Mod1) * P + b[i] - '0') % Mod1;
HashB2 = (((HashB2 - Pow2 * (b[i-NA] - '0')) % Mod2 + Mod2) * P + b[i] - '0') % Mod2;
if(HashA1 == HashB1 && HashA2 == HashB2)
v.push_back(i-NA+1);
}
fout<<v.size()<<'\n';
for(int i=0;i<min(1000, (int)v.size());i++)
fout<<v[i]<<' ';
return 0;
}