Pagini recente » Cod sursa (job #2024395) | Cod sursa (job #1944714) | Clasament ae | Cod sursa (job #1057264) | Cod sursa (job #3279853)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 1000;
const int MOD=101, BASE=257, CASE = 263;
int maxBaseInMod = 1, maxCaseInMod = 1;
int hashA = 0, nhashA=0 , curHashB = 0, nHashB = 0;
int a, b;
string A, B;
vector<int> matches;
void findie(int i)
{
for(int j=0; j<a; j++)
if(A[j]!=B[j+i])
return;
matches.push_back(i);
}
int main()
{
fin >> A >> B;
a=A.size();
b=B.size();
if (a > b)
{
fout << "0";
return 0;
}
for (int i=1; i<a; i++)
{
maxBaseInMod = (maxBaseInMod * BASE) % MOD;
maxCaseInMod = (maxCaseInMod* CASE) %MOD;
}
for(int i=0; i<a; i++)
{
curHashB = (curHashB * BASE + B[i]) % MOD;
nHashB = (nHashB * CASE + B[i]) % MOD;
hashA = (hashA * BASE + A[i]) % MOD;
nhashA = (nhashA * CASE +A[i]) %MOD;
}
for(int i=a; i<=b; i++)
{
if(hashA == curHashB && nhashA == nHashB)
findie(i-a);
if(i<b)
{
curHashB = (curHashB + MOD - (maxBaseInMod * B[i - a]) % MOD) % MOD;
curHashB = (curHashB * BASE + B[i]) % MOD;
nHashB = (nHashB + MOD - (maxCaseInMod * B[i - a]) % MOD) % MOD;
nHashB = (nHashB * CASE + B[i]) % MOD;
}
}
fout << matches.size() << '\n';
int n=0;
for(auto a: matches)
{
if(n>=1000)
break;
n++;
fout << a << ' ';
}
return 0;
}