Pagini recente » Cod sursa (job #2931473) | Cod sursa (job #2539411) | Cod sursa (job #1971577) | Cod sursa (job #1256762) | Cod sursa (job #3038098)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define LLI long long int
#define P 73
#define MOD1 100007
#define MOD2 100021
int main()
{
string s1, s2;
fin >> s1 >> s2;
int hashA1 = 0, hashA2 = 0;
int subP1 = 1, subP2 = 1;
if (s1.length() > s2.length())
{
cout << "0\n";
return 0;
}
for (int i = 0; i < s1.length(); i++)
{
hashA1 = (hashA1 * P + s1[i]) % MOD1;
hashA2 = (hashA2 * P + s1[i]) % MOD2;
if (i != 0)
subP1 = (subP1 * P) % MOD1,
subP2 = (subP2 * P) % MOD2;
}
int hashB1 = 0, hashB2 = 0;
for (int i = 0; i < s1.length(); i++)
{
hashB1 = (hashB1 * P + s2[i]) % MOD1;
hashB2 = (hashB2 * P + s2[i]) % MOD2;
}
int res = 0;
vector<int> indx;
if (hashA1 == hashB1 && hashA2 == hashB2)
res++, indx.push_back(0);
for (int i = s1.length(); i < s2.length(); i++)
{
hashB1 = ((hashB1 - (s2[i - s1.length()] * subP1) % MOD1 + MOD1) * P + s2[i]) % MOD1;
hashB2 = ((hashB2 - (s2[i - s1.length()] * subP2) % MOD2 + MOD2) * P + s2[i]) % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2)
res++, indx.push_back(i - s1.length());
}
fout << res << "\n";
for (int i = 0; i < indx.size() && i < 1000; i++)
fout << indx[i] + 1 << " ";
return 0;
}