Pagini recente » Borderou de evaluare (job #2058351) | Borderou de evaluare (job #2401130) | Borderou de evaluare (job #3157985) | Borderou de evaluare (job #1418894) | Cod sursa (job #1967141)
#include <iostream>
#include <fstream>
#include <vector>
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define FORR(i, x, y) for(int i = x; i >= y; --i)
#define pb(x) push_back(x)
#define sz() size()
#define mod1 67
#define mod2 71
using namespace std;
int v[130];
string A, B;
void set_poz()
{
int nr = 0;
FOR(i, 48, 57)
v[i] = ++nr;
FOR(i, 65, 90)
v[i] = ++nr;
FOR(i, 97, 122)
v[i] = ++nr;
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int m, n, base = 63, p1 = 1, p2 = 1, a1 = 0, b1 = 0, a2 = 0, b2 = 0;
vector <int> sol;
set_poz();
fin >> A >> B;
m = A.sz() - 1;
n = B.sz() - 1;
if(n < m){
fout << 0;
return 0;
}
FOR(i, 0, m){
a1 = (base * a1 + v[int(A[i])]) % mod1;
b1 = (base * b1 + v[int(B[i])]) % mod1;
a2 = (base * a2 + v[int(A[i])]) % mod2;
b2 = (base * b2 + v[int(B[i])]) % mod2;
if(i != 0){
p1 = (base * p1) % mod1;
p2 = (base * p2) % mod2;
}
}
FOR(i, 0, n - m){
if(a1 == b1 && a2 == b2) sol.pb(i);
b1 = ((b1 - (v[int(B[i])] * p1) % mod1 + mod1) * base + v[int(B[i + m + 1])]) % mod1;
b2 = ((b2 - (v[int(B[i])] * p2) % mod2 + mod2) * base + v[int(B[i + m + 1])]) % mod2;
}
fout << sol.sz() << '\n';
int x = sol.sz() - 1;
if(sol.sz() != 0)
FOR(i, 0, min(x, 999))
fout << sol[i] << ' ';
return 0;
}