Pagini recente » Cod sursa (job #3154909) | Cod sursa (job #995009) | Cod sursa (job #1553036) | Cod sursa (job #1971589) | Cod sursa (job #1784279)
//
// main.cpp
// BinarySearch
//
// Created by Cristina Radulescu on 10/18/16.
// Copyright © 2016 Cristina Radulescu. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define MOD 100103;
void strmatch(string A, string B){
vector<int> v;
int count = 0;
int p = 26, p1 = 1, p2 = 1;
int hashA = 0, hashB = 0;
int sizeA = A.size(), sizeB = B.size();
for(int i = 0; i < sizeA; ++i){
hashA = (hashA * p + A[i]) % MOD;
hashB = (hashB * p + B[i]) % MOD;
if(i != 0){
p1 = (p1 * p) % MOD;
p2 = (p2 * p) % MOD;
}
}
if(hashA == hashB){
v.push_back(0);
count++;
}
for(int i = sizeA; i < sizeB && count < 1001 ; ++i){
hashB = ((hashB - B[i-sizeA] * p1) * p + B[i]) % MOD;
if(hashB == hashA){
v.push_back(i-sizeA+1);
count++;
}
}
cout << count << endl;
for(int i = 0; i < count; ++i)
cout << v[i] << " ";
}
int main() {
// insert code here...
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out","w", stdout);
string A, B;
cin >> A >> B;
strmatch(A, B);
return 0;
}