Nu aveti permisiuni pentru a descarca fisierul grader_test8.ok
Cod sursa(job #1933764)
Utilizator | Data | 20 martie 2017 22:06:56 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 14 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.49 kb |
#include <bits/stdc++.h>
using namespace std;
const int mod1 = 666013;
const int mod2 = 666015;
long long h1, h2;
long long a1, a2;
vector<int> ret;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A; f >> A;
int n = A.size();
string B; f >> B;
int m = B.size();
if(n > m) {
g << "0\n";
return 0;
}
long long p1 = 1, p2 = 1;
h1 = (A[0] - 'A' + 1);
h2 = (A[0] - 'A' + 1);
for(int i = 1; i < n; i ++) {
p1 *= 31; p1 %= mod1;
p2 *= 31; p2 %= mod2;
h1 = (h1 * 31 + (A[i] - 'A' + 1)) % mod1;
h2 = (h2 * 31 + (A[i] - 'A' + 1)) % mod2;
}
a1 = (B[0] - 'A' + 1);
a2 = (B[0] - 'A' + 1);
for(int i = 1; i < n; i ++) {
a1 = (a1 * 31 + (B[i] - 'A' + 1)) % mod1;
a2 = (a2 * 31 + (B[i] - 'A' + 1)) % mod2;
}
if(a1 == h1 && a2 == h2) {
ret.push_back(0);
}
for(int i = n; i < m; i ++) {
a1 = (a1 - (B[i - n] - 'A' + 1) * p1) % mod1;
a2 = (a2 - (B[i - n] - 'A' + 1) * p2) % mod2;
a1 = (a1 * 31 + (B[i] - 'A' + 1)) % mod1;
a2 = (a2 * 31 + (B[i] - 'A' + 1)) % mod2;
if(a1 == h1 && a2 == h2) {
ret.push_back(i - n + 1);
if(ret.size() == 1000) {
break;
}
}
}
g << ret.size() << "\n";
for(int i = 0; i < ret.size(); i ++) g << ret[i] << " ";
g << "\n";
return 0;
}