Pagini recente » Cod sursa (job #375727) | Cod sursa (job #2275041) | Cod sursa (job #1665978) | Cod sursa (job #2807385) | Cod sursa (job #2358994)
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 2000005
#define MOD 101
#define crypt 256
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[NMAX], sir2[NMAX];
vector<int> rez;
int h = 1, lg1, lg2;
int rehash(int val, int poz)
{
val = (crypt * (val - sir2[poz] * h) + sir2[poz + lg1]) % MOD;
return val;
}
void match()
{
int hs1 = 0;
int hs2 = 0;
for(int i = 0; i < lg1; ++i)
{
hs1 = (hs1 * crypt + sir1[i]) % MOD;
hs2 = (hs2 * crypt + sir2[i]) % MOD;
}
for(int i = 0; i <= lg2 - lg1; ++i)
{
if(hs1 == hs2)
{
bool ok = 1;
for(int j = 0; j < lg1; ++j)
if(sir1[j] != sir2[i + j])
{
ok = 0;
break;
}
if(ok)
rez.push_back(i);
}
if(i < lg2 - lg1)
{
hs2 = rehash(hs2, i);
if(hs2 < 0)
hs2 = (hs2 + MOD);
}
}
}
int main()
{
fin.getline(sir1, NMAX);
fin.getline(sir2, NMAX);
lg1 = strlen(sir1);
lg2 = strlen(sir2);
for(int i = 0; i < lg1 - 1; ++i)
h = (h * crypt) % MOD;
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;
}