Pagini recente » Cod sursa (job #2034622) | Cod sursa (job #693007) | Cod sursa (job #532958) | Cod sursa (job #2465027) | Cod sursa (job #2359016)
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 2000005
#define MOD1 100007
#define MOD2 100021
#define crypt 256
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[NMAX], sir2[NMAX];
vector<int> rez;
int h1 = 1, h2 = 1, lg1, lg2;
void match()
{
int hs1 = 0;
int hs2 = 0;
for(int i = 0; i < lg1; ++i)
{
hs1 = (hs1 * crypt + sir1[i]) % MOD1;
hs2 = (hs2 * crypt + sir1[i]) % MOD2;
}
int sh1 = 0;
int sh2 = 0;
for(int i = 0; i < lg1; ++i){
sh1 = (sh1 * crypt + sir2[i]) % MOD1;
sh2 = (sh2 * crypt + sir2[i]) % MOD2;
}
for(int i = 0; i <= lg2 - lg1; ++i)
{
if(sh1 == hs1 && sh2 == hs2)
rez.push_back(i);
if(i < lg2 - lg1)
{
sh1 = (crypt * (sh1 - sir2[i] * h1) + sir2[i + lg1]) % MOD1;
sh2 = (crypt * (sh2 - sir2[i] * h2) + sir2[i + lg1]) % MOD2;
if(sh1 < 0)
sh1 = (sh1 + MOD1);
if(sh2 < 0)
sh2 = (sh2 + MOD2);
}
}
}
int main()
{
fin.getline(sir1, NMAX);
fin.getline(sir2, NMAX);
lg1 = strlen(sir1);
lg2 = strlen(sir2);
for(int i = 0; i < lg1 - 1; ++i)
h1 = (h1 * crypt) % MOD1, h2 = (h2 * crypt) % MOD2;
match();
fout << rez.size() << '\n';
int stop = min((int)rez.size(), 1000);
for(int i = 0; i < stop; ++i)
fout << rez[i] << ' ';
fout << '\n';
return 0;
}