Pagini recente » Cod sursa (job #743062) | Cod sursa (job #2368946) | Cod sursa (job #676375) | Cod sursa (job #2354020) | Cod sursa (job #827636)
Cod sursa(job #827636)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000100
#define key1 100007
#define key2 100021
#define base1 73
#define base2 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int solution[1011];
char A[NMAX], B[NMAX];
int length1, length2;
int code_A1, code_A2;
int code_B1, code_B2;
int P1 = 1, P2 = 1;
int main()
{
fin >> A >> B;
length1 = strlen(A);
length2 = strlen(B);
if (length1 > length2)
{
fout << "0\n";
return 0;
}
for (int i = 0; i < length1; ++i)
{
code_A1 = code_A1 * base1 + A[i];
code_A2 = code_A2 * base2 + A[i];
code_B1 = code_B1 * base1 + B[i];
code_B2 = code_B2 * base2 + B[i];
code_A1 %= key1;
code_A2 %= key2;
code_B1 %= key1;
code_B2 %= key2;
if (i > 0)
{
P1 = P1 * base1;
P2 = P2 * base2;
}
P1 %= key1;
P2 %= key2;
}
for (int i = length1; i <= length2; ++i)
{
if (code_A1 == code_B1 && code_A2 == code_B2)
{
if (solution[0] < 1000)
{
solution[++solution[0]] = i - length1;
}
else break;
}
code_B1 = base1 * (code_B1 - P1 * (B[i - length1])) + B[i];
code_B2 = base2 * (code_B2 - P2 * (B[i - length1])) + B[i];
code_B1 %= key1;
code_B2 %= key2;
if (code_B1 < 0) code_B1 += key1;
if (code_B2 < 0) code_B2 += key2;
}
fout << solution[0] << '\n';
for (int i = 1; i <= solution[0]; ++i)
{
fout << solution[i] << ' ';
}
fout.close();
return 0;
}