Pagini recente » Cod sursa (job #498850) | Cod sursa (job #1103772) | Cod sursa (job #2976983) | Cod sursa (job #2920235) | Cod sursa (job #2284471)
#include <iostream>
#include <fstream>
#include <math.h>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000045], B[2000045];
int n1 = 3, m1 = 200001, n2 = 5, m2 = 2000001, hashA = 0, hashB = 0, sol = 0;
int pos[2000045];
int Hash(char str[], int n, int m, int hashul, int len)
{
for (int i = 0; i < len; ++i){
hashul *= n1;
hashul += str[i];
}
hashul = hashul%m;
return hashul;
}
void Solve()
{
int a_len = strlen(A);
int b_len = strlen(B);
hashA = Hash(A, n1, m1, hashA, a_len);
hashB = Hash(B, n2, m2, hashB, b_len);
for (int i = 0, oh = 0; i < strlen(B) - a_len; ++i){
char str[a_len];
for (int j = i, k = 0; j < i + a_len; ++j, ++k)
str[k] = B[j];
int hasul = 0;
hasul = Hash(str, n1, m1, hasul, strlen(str));
if (hashA == hasul){
++sol;
pos[oh] = i;
++oh;
}
}
}
void Read()
{
fin.getline(A, 2000045);
fin.getline(B, 2000045);
}
void Write()
{
fout << sol << "\n";
for (int i = 0; i < sol; ++i)
fout << pos[i] << " ";
}
int main()
{
Read();
Solve();
Write();
return 0;
}