Pagini recente » Cod sursa (job #120193) | Cod sursa (job #2311347) | Cod sursa (job #1401834) | Cod sursa (job #33587) | Cod sursa (job #2211188)
#include <fstream>
#include <vector>
#include <cstring>
#define Mod2 666013
#define Mod1 10003
#define in1 127
#define in2 131
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
vector <int> s;
int n, m, x1, x2, y1, y2, p1, p2;
char A[2000002];
char B[2000002];
int main()
{
f.getline(A,2000002);
f.getline(B,2000002);
n = strlen(A);
m = strlen(B);
if (n > m)
{
g << 0 << '\n';
}
else
{
///127 131
for (int i = 0; i < n; i++)
{
x1 = ((x1 * in1) % Mod1 + (A[i] - '0')) % Mod1;
x2 = ((x2 * in2) % Mod2 + (A[i] - '0')) % Mod2;
y1 = ((y1 * in1) % Mod1 + (B[i] - '0')) % Mod1;
y2 = ((y2 * in2) % Mod2 + (B[i] - '0')) % Mod2;
}
p1 = p2 = 1;
for (int i = 1; i < n; i++)
{
p1 = (p1 * in1) % Mod1;
p2 = (p2 * in2) % Mod2;
}
if (x1 == y1 && x2 == y2)
{
s.push_back(0);
}
for (int i = n; i < m; i++)
{
y1 = ((y1 - (p1 * (B[i - n] - '0')) % Mod1 + Mod1) * in1 + (B[i] - '0')) % Mod1;
y2 = ((y2 - (p2 * (B[i - n] - '0')) % Mod2 + Mod2) * in2 + (B[i] - '0')) % Mod2;
if (y1 == x1 && y2 == x2)
{
s.push_back(i - n + 1);
}
}
g << s.size() << '\n';
for (int i = 0; i < 1000 && i < s.size(); i++)
{
g << s[i] << " ";
}
}
return 0;
}