Pagini recente » Cod sursa (job #1131648) | Cod sursa (job #3131946) | Cod sursa (job #572048) | Cod sursa (job #925945) | Cod sursa (job #827648)
Cod sursa(job #827648)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000100
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int solution[1011];
char A[NMAX], B[NMAX];
int length1, length2;
int main()
{
int hash_num = 3;
int key[] = {0, 10107, 10119, 10103};
int base[] = {0, 22, 22, 22};
int codeA[] = {0, 0, 0, 0};
int codeB[] = {0, 0, 0, 0};
int P[100] = {0, 1, 1, 1};
fin >> A >> B;
length1 = strlen(A);
length2 = strlen(B);
if (length1 > length2)
{
fout << "0\n";
return 0;
}
for (int i = 0; i < length1; ++i)
{
for (int j = 1; j <= hash_num; ++j)
{
codeA[j] = codeA[j] * base[j] + A[i] - '0';
codeB[j] = codeB[j] * base[j] + B[i] - '0';
codeA[j] %= key[j];
codeB[j] %= key[j];
if (i > 0) P[j] *= base[j];
P[j] %= key[j];
}
}
for (int i = length1; i <= length2; ++i)
{
bool ok = true;
for (int j = 1; j <= hash_num && ok; ++j)
{
if (codeA[j] != codeB[j]) ok = false;
}
if (ok)
{
if (solution[0] < 1000)
{
solution[++solution[0]] = i - length1;
}
else solution[0]++;
}
for (int j = 1; j <= hash_num; ++j)
{
codeB[j] = base[j] * (codeB[j] - P[j] * (B[i - length1] - '0')) + B[i] - '0';
codeB[j] %= key[j];
if (codeB[j] < 0) codeB[j] += key[j];
}
}
fout << solution[0] << '\n';
for (int i = 1; i <= min(solution[0], 1000); ++i)
{
fout << solution[i] << ' ';
}
fout.close();
return 0;
}