Pagini recente » Cod sursa (job #2395339) | Cod sursa (job #3244558) | Cod sursa (job #1938766) | Cod sursa (job #2699624) | Cod sursa (job #827620)
Cod sursa(job #827620)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 2000100
#define key1 101007
#define key2 101019
#define base1 73
#define base2 79
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] - '0';
code_A2 = code_A2 * base2 + A[i] - '0';
code_B1 = code_B1 * base1 + B[i] - '0';
code_B2 = code_B2 * base2 + B[i] - '0';
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;
}
}
code_B1 = base1 * (code_B1 - P1 * (B[i - length1] - '0')) + B[i] - '0';
code_B2 = base2 * (code_B2 - P2 * (B[i - length1] - '0')) + B[i] - '0';
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;
}