Pagini recente » Cod sursa (job #225755) | Cod sursa (job #196373) | Cod sursa (job #1011801) | Cod sursa (job #1139383) | Cod sursa (job #3214396)
#include <bits/stdc++.h>
#define P 123457
#define Q 777013
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, cnt, codA1, codA2, codB1, codB2, p1, p2;
int cod[256];
int sol[1005];
char a[2000005], b[2000005];
int main()
{
int i;
fin >> a;
fin >> b;
n = strlen(a);
m = strlen(b);
p1 = p2 = 1;
for (i = 0; i < n; i++)
{
codA1 = (codA1 * 73 + a[i]) % P;
codA2 = (codA2 * 73 + a[i]) % Q;
codB1 = (codB1 * 73 + b[i]) % P;
codB2 = (codB2 * 73 + b[i]) % Q;
if (i > 0)
{
p1 = (p1 * 73) % P;
p2 = (p2 * 73) % Q;
}
}
if (codA1 == codB1 && codA2 == codB2)
{
cnt++;
sol[cnt] = 0;
}
for (i = n; i < m; i++)
{
codB1 = (((codB1 - b[i - n] * p1) % P + P) * 73 + b[i]) % P;
codB2 = (((codB2 - b[i - n] * p2) % Q + Q) * 73 + b[i]) % Q;
if (codA1 == codB1 && codA2 == codB2)
{
cnt++;
sol[cnt] = i - n + 1;
}
}
fout << cnt << "\n";
for (i = 1; i <= min(cnt, 1000); i++)
fout << sol[i] << " ";
fout << "\n";
fin.close();
fout.close();
return 0;
}