Pagini recente » Cod sursa (job #2223731) | Profil rockoana | Cod sursa (job #1279280) | Cod sursa (job #1176091) | Cod sursa (job #3214458)
#include <bits/stdc++.h>
#define ll unsigned long long
#define M1 1000000007
#define M2 1000000009
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
ll P1 = 307, P2 = 317, lastBase1, c, hashA1, hashB1, invP1, n, hashA2, hashB2, lastBase2, invP2;
vector<int> res;
ll logput(ll x, ll exp, ll M)
{
ll aux = 1;
while(exp)
{
if(exp % 2)
aux = aux * x % M;
exp /= 2;
x = x * x % M;
}
return aux;
}
ll makeHash(string s, int start, int stop, ll P, ll M)
{
ll rez = 0;
ll aux = 1;
for(int i = start; i < stop; i++)
{
rez = (rez + (aux * s[i] % M)) % M;
aux = aux * P % M;
}
return rez;
}
bool check(int st)
{
int i = 0;
while(i < a.length())
{
if(a[i] != b[st])
return 0;
i++;
st++;
}
return 1;
}
int main()
{
fin >> a >> b;
lastBase1 = logput(P1, a.length() - 1, M1);
invP1 = logput(P1, M1 - 2, M1);
lastBase2 = logput(P2, a.length() - 1, M2);
invP2 = logput(P2, M2 - 2, M2);
if(a.length() > b.length())
{
fout << 0;
return 0;
}
hashA1 = makeHash(a, 0, a.length(), P1, M1);
hashB1 = makeHash(b, 0, a.length(), P1, M1);
hashA2 = makeHash(a, 0, a.length(), P2, M2);
hashB2 = makeHash(b, 0, a.length(), P2, M2);
for(int i = a.length() - 1; i < b.length(); i++)
{
if(hashA1 == hashB1 && hashA2 == hashB2 && check(i - a.length() + 1))
res.push_back(i - a.length() + 1);
hashB1 = (hashB1 - b[i - a.length() + 1] + M1) % M1;
hashB1 = hashB1 * invP1 % M1;
hashB1 = (hashB1 + b[i + 1] * lastBase1 % M1) % M1;
hashB2 = (hashB2 - b[i - a.length() + 1] + M2) % M2;
hashB2 = hashB2 * invP2 % M2;
hashB2 = (hashB2 + b[i + 1] * lastBase2 % M2) % M2;
}
fout << res.size() << '\n';
n = res.size();
if(res.size() > 1000)
n = 1000;
for(int i = 0; i < n; i++)
fout << res[i] << ' ';
return 0;
}