Pagini recente » Cod sursa (job #682066) | Cod sursa (job #1744523) | Cod sursa (job #904134) | Cod sursa (job #947604) | Cod sursa (job #2097927)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int Mod1 = 123457;
const int Mod2 = 100007;
const int Nmax = 2000001;
string a, b;
int n, m, p1, p2;
bool viz[Nmax];
int main()
{
int hashA1, hashA2, hashB1, hashB2, sol, k;
fin >> a >> b;
n = a . size();
m = b . size();
if(n > m)
{
fout << "0\n";
return 0;
}
p1 = p2 = 1;
hashA1 = hashA2 = 0;
for(int i = 0 ; i < n ; i++)
{
///hashing perfect
hashA1 = (hashA1 * 26 + a[i]) % Mod1;
hashA2 = (hashA2 * 26 + a[i]) % Mod2;
if(i > 0)
{
p1 = (p1 * 26) % Mod1;
p2 = (p2 * 26) % Mod2;
}
}
hashB1 = hashB2 = 0;
for(int i = 0 ; i < n ; i++)
{
hashB1 = (hashB1 * 26 + b[i]) % Mod1;
hashB2 = ( hashB2 * 26 + b[i]) % Mod2;
}
sol = k = 0;
if(hashA1 == hashB1 && hashA2 == hashB2)
{
viz[k] = true;
sol ++;
}
for(int i = n ; i < m ; i++)
{
hashB1 = ((hashB1 - (b[i - n] * p1) % Mod1 + Mod1) * 26 + b[i]) % Mod1;
hashB2 = ((hashB2 - (b[i - n] * p2) % Mod2 + Mod2) * 26 + b[i]) % Mod2;
++k;
if(hashA1 == hashB1 && hashA2 == hashB2)
{
viz[k] = true;
sol ++;
}
}
fout << sol << "\n";
int pas = 0;
for(int i = 0 ; i < m && pas < 1000; i++)
if(viz[i] == true)
{
fout << i << " ";
pas ++ ;
}
fin.close();
fout.close();
return 0;
}