Pagini recente » Cod sursa (job #226282) | Istoria paginii runda/winners28/clasament | Cod sursa (job #493823) | Cod sursa (job #880199) | Cod sursa (job #2258639)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define MAX 10000
int main()
{
long long int v1 = 0, v2 = 0;
long long int h1 = 0, h2 = 0;
string a, b;
in >> a;
in >> b;
int n = a.length();
int m = b.length();
int p1 = 1, p2 = 1;
for(int i = n-1; i >= 0; --i){
v1 += a[i] * p1;
p1 *= 27;
}
for(int i = n-1; i >= 0; --i){
v2 += a[i] * p2;
p2 *= 29;
}
v1 = v1 % 10007;
v2 = v2 % 666013;
int c = 0;
int r = 0;
int is[MAX];
for(int i = 0; i < m; ++i){
if(i <= m-n){
string substring = "";
h1 = 0;
h2 = 0;
p1 = 1;
p2 = 1;
for(int j = i; j < n+i; ++j){
substring += b[j];
}
for(int j = substring.length()-1; j >= 0; --j){
h1 += substring[j] * p1;
p1 *= 27;
h2 += substring[j] * p2;
p2 *= 29;
}
h1 = h1 % 10007;
h2 = h2 % 666013;
if(h1 == v1 && h2 == v2){
c++;
is[r] = i;
r++;
}
}
}
out << c << '\n';
for(int i = 0; i < r; ++i){
out << is[i] << " ";
}
}