Pagini recente » Cod sursa (job #3181337) | Cod sursa (job #1644387) | Cod sursa (job #3269249) | Istoria paginii runda/arhiva-utcn | Cod sursa (job #918269)
Cod sursa(job #918269)
//#ifndef LINUX
//#include "stdafx.h"
//#endif
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const char *in = "strmatch.in", *out = "strmatch.out";
const int P = 101, MOD1 = 100007, MOD2 = 100021;
int nr = 0;
string A, B;
vector<int> v;
void citire() {
ifstream fin(in);
fin >> A >> B;
}
void afisare() {
ofstream fout(out);
fout << nr << "\n";
for(int i = 0; i < v.size(); ++i)
fout << v[i] << " ";
}
void solve() {
int N = A.size(), M = B.size();
if(N > M) {
ofstream fout(out);
fout << "0" << endl;
exit(0);
}
int P1 = 1;
int hashA = 0;
for(int i = 0; i < N; ++i) {
hashA = (hashA * P + A[i]) % MOD1;
if(i != 0)
P1 = (P1 * P) % MOD1;
}
int hash1 = 0;
for(int i = 0; i < N; ++i)
hash1 = (hash1 * P + B[i]) % MOD1;
if(hash1 == hashA && equal(A.begin(), A.end(), B.begin()))
v.push_back(0);
for(int i = N; i < M; ++i) {
hash1 = ( (hash1 - (B[i - N] * P1) % MOD1 + MOD1) * P + B[i] ) % MOD1;
if(hash1 == hashA && equal(A.begin(), A.end(), B.begin() + i - N + 1)) {
if(v.size() < 1000)
v.push_back(i - N + 1);
++nr;
}
}
}
int main() {
citire();
solve();
afisare();
return 0;
}