Pagini recente » Borderou de evaluare (job #2625485) | Cod sursa (job #1018062) | Borderou de evaluare (job #2271228) | Borderou de evaluare (job #1373940) | Cod sursa (job #1967135)
#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])
return 0;
return 1;
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.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;
if(i != 0)
p = (base * p) % mod;
}
FOR(i, 0, n - m){
if(a == b && it_match(i, i + m)) sol.pb(i);
b = ((b - (v[int(B[i])] * p) % mod + mod) * base + v[int(B[i + m + 1])]) % mod;
}
fout << sol.sz() << '\n';
int x = sol.sz() - 1;
if(sol.sz() != 0)
FOR(i, 0, min(x, 999))
fout << sol[i] << ' ';
return 0;
}