Pagini recente » Cod sursa (job #304322) | Cod sursa (job #1310503) | Cod sursa (job #2163318) | Cod sursa (job #2177054) | Cod sursa (job #2196541)
#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) % M1, p2 = (p2 * B2) % M2;
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;
}