Pagini recente » Cod sursa (job #406201) | Cod sursa (job #1147957) | Cod sursa (job #2690154) | Cod sursa (job #1709245) | Cod sursa (job #2284623)
#include <iostream>
#include <fstream>
#include <cstring>
#include <math.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000045], B[2000045];
int n = 3, m = 20000001, hashA = 0, hashB = 0, sol = 0;
int pos[2000045];
int meMario(int nr, int put)
{
int result = 1;
for (int i = 0; i < put; ++i)
result *= nr;
return result;
}
int Hash(char str[], int n, int m, int hashul, int len)
{
for (int i = 0; i < len; ++i){
hashul *= n;
hashul += str[i];
hashul %= m;
}
return hashul;
}
int Niext(int hashul, int position, int len)
{
hashul -= (B[position-1] * meMario(n, len-1));
hashul *= n;
hashul += B[position+2];
hashul %= m;
return hashul;
}
void Solve()
{
int a_len = strlen(A);
int oh = 0;
hashA = Hash(A, n, m, hashA, a_len);
char str[a_len];
for (int i = 0; i < a_len; ++i)
str[i] = B[i];
int hashul = 0;
hashul = Hash(str, n, m, hashul, a_len);
if (hashA == hashul){
++sol;
pos[oh] = 0;
++oh;
}
for (int i = 1; i <= strlen(B) - a_len; ++i){
hashul = Niext(hashul, i, a_len);
if (hashA == hashul){
++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;
}