Pagini recente » Cod sursa (job #2639460) | Cod sursa (job #1945190) | Cod sursa (job #2678970) | Cod sursa (job #1659260) | Cod sursa (job #768170)
Cod sursa(job #768170)
#include <stdio.h>
#include <string>
#include <fstream>
#define MOD 1000000001
#define BASE 131
using namespace std;
string Str, subStr;
int sL, subL;
long long hash[2000000], hashS;
int nr, Sol[1001];
void read_() {
ifstream fin("strmatch.in");
fin >> subStr;
fin >> Str;
sL = Str.length();
subL = subStr.length();
fin.close();
}
void search() {
for (int i = subL - 1; i < sL; i++) {
if (hash[i] == hashS) {
if (nr < 1000) {
Sol[nr] = i - subL + 1;
}
nr++;
}
}
}
void printHash(){
for (int i = 0; i < sL; i++) {
printf("%d %c %d; ", i, Str[i], hash[i]);
}
printf("\n%d\n\n", hashS);
}
void get_hash() {
long long S = 0;
for (int i = 0; i < subL; i++) {
S = S * BASE + Str[i];
S %= MOD;
hash[i] += S;
hashS = (hashS * BASE + subStr[i]) % MOD;
}
long long pw = 1;
for (int i = 0; i < subL; i++) {
pw = (pw * BASE) % MOD;
}
for (int i = subL; i < sL; i++) {
hash[i] = (((hash[i-1] * BASE + Str[i]) % MOD) - (pw * Str[i - subL])) % MOD;
if (hash[i] < 0) {
hash[i] += MOD;
}
}
//printHash();
}
void printSol() {
printf("%d\n", nr);
if (nr > 1000) {
nr = 1000;
}
for (int i = 0; i < nr; i++) {
printf("%d ", Sol[i]);
}
}
int main(){
freopen("strmatch.out", "w", stdout);
read_();
get_hash();
search();
printSol();
return 0;
}