Pagini recente » Borderou de evaluare (job #975980) | Borderou de evaluare (job #2155263) | Borderou de evaluare (job #1131770) | Borderou de evaluare (job #2256223) | Cod sursa (job #1967106)
#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 mod 67
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 it_match(int x, int y)
{
FOR(i, x, y)
if(A[i - x] != B[i]) {
cout << i << ' ';
return 0;
}
return 1;
}
int main()
{
ifstream fin("strmach.in");
ofstream fout("strmach.out");
int m, n, base = 63, p = 1, a = 0, b = 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){
a = (base * a + v[int(A[i])]) % mod;
b = (base * b + v[int(B[i])]) % mod;
p *= base;
}
p /= base;
FOR(i, 0, n - m){
if(a == b && it_match(i, i + m)) sol.pb(i);
b = ((b - (v[B[i]] * p) % mod + mod) * base + v[B[i + m + 1]]) % mod;
}
fout << sol.sz() << '\n';
if(sol.sz() != 0)
FOR(i, 0, sol.sz() - 1)
fout << sol[i] << ' ';
return 0;
}