Pagini recente » Cod sursa (job #2859698) | Cod sursa (job #2690852) | Cod sursa (job #1449138) | Cod sursa (job #1651177) | Cod sursa (job #2196521)
#include <bits/stdc++.h>
#define M1 666013
#define M2 10013
#define B1 127
#define B2 131
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int ss1, ss2, s1, s2;
vector<int> s;
char sstr[2000003], str[2000003];
int main()
{
f >> sstr >> str;
int N = strlen(sstr), M = strlen(str);
for(int i = 0; i < N; i++)
ss1 = (ss1 * B1 % M1 + (sstr[i] - '0')) % M1,
ss2 = (ss2 * B2 % M2 + (sstr[i] - '0')) % M2,
s1 = (s1 * B1 % M1 + (str[i] - '0')) % M1,
s2 = (s2 * B2 % M2 + (str[i] - '0')) % M2;
int p1 = 1, p2 = 1;
for(int i = 1; i < N; i++)
p1 = p1 * B1, p2 = p2 * B2;
if(ss1 == s1 && ss2 == s2)
s.push_back(0);
for(int i = N; i < M; i++) {
s1 = (((s1 - (str[i - N] - '0') * p1) % M1 + M1) * B1 + (str[i] - '0')) % M1;
s2 = (((s2 - (str[i - N] - '0') * p2) % M2 + M2) * B2 + (str[i] - '0')) % M2;
if(ss1 == s1 && ss2 == s2)
s.push_back(i - N + 1);
}
g << s.size() << "\n";
for(int i = 0; i < s.size() && i < 1000; i++)
g << s[i] << " ";
g << "\n";
return 0;
}