Pagini recente » Cod sursa (job #1084126) | Cod sursa (job #2516026) | Cod sursa (job #2507809) | Cod sursa (job #2999277) | Cod sursa (job #768279)
Cod sursa(job #768279)
#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(int i) {
if (hash[i] == hashS) {
if (nr < 1000) {
Sol[nr] = i - subL + 1;
}
nr++;
}
}
void searchComplete() {
for (int i = subL - 1; i < sL; i++) {
if (hash[i] == hashS) {
if (Str.compare(i - subL + 1, subL, subStr) == 0) {
if (nr < 1000) {
Sol[nr] = i - subL + 1;
}
nr++;
}
}
}
}
void get_Rolling_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;
}
search(subL - 1);
for (int i = subL; i < sL; i++) {
hash[i] = ((hash[i-1] * BASE + Str[i]) - (pw * Str[i - subL])) % MOD;
if (hash[i] < 0) {
hash[i] += MOD;
}
search(i);
}
}
void get_Easy_Hash() {
int S = 0;
for (int i = 0; i < subL; i++) {
S += Str[i];
hash[i] += S;
hashS += subStr[i];
}
for (int i = subL; i < sL; i++) {
hash[i] = hash[i-1] + Str[i] - Str[i - subL];
}
searchComplete();
}
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_();
if (sL > 2 * subL) {
// Are rost sa folosesc o fct de hash mai complexa
get_Rolling_Hash();
} else {
// Pierd prea mult timp cu fuctia de hash => folosesc una mai simpla.
get_Easy_Hash();
}
printSol();
return 0;
}