Pagini recente » Cod sursa (job #2219683) | Cod sursa (job #3190540) | Statistici Stefan Cheroiu-Cozma (UVT_CHEROIU-COZMA_STEFAN) | Cod sursa (job #2215468) | Cod sursa (job #2084090)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#define Nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int p = 127;
long long hash1, hash2, p2 = 1;
vector<int>sol;
int n, m;
char a[Nmax], b[Nmax];
int main()
{
fin >> a;
fin >> b;
n = strlen(a);
m = strlen(b);
hash1 = 0;
hash2 = 0;
for(int i = 0; i < n; i++)
hash1 = hash1 * p + a[i];
for(int i = 0; i < n; i++)
hash2 = hash2 * p + b[i];
for(int i = 1; i < n; i++)
p2 = p2 * p;
if(hash1 == hash2)sol.push_back(0);
for(int i = n; i < m; i++)
{
hash2 -= p2 * b[i - n];
hash2 = hash2 * p + b[i];
if(hash1 == hash2)sol.push_back(i - n + 1);
}
fout << sol.size() << '\n';
for(int i = 0 ; i < sol.size() && i < 1000; i++)
fout << sol[i] << " ";
return 0;
}