Pagini recente » Cod sursa (job #815391) | Cod sursa (job #2551988) | Cod sursa (job #2883659) | Cod sursa (job #459193) | Cod sursa (job #768315)
Cod sursa(job #768315)
#include <stdio.h>
#include <string>
#include <fstream>
#define MOD 1000000001
#define BASE 131
#define easyT 1
#define RollT 2
using namespace std;
string Str, subStr;
int sL, subL;
long long hashSubS, hashS;
int nr, Sol[1001];
int T;
void read_() {
ifstream fin("strmatch.in");
fin >> subStr;
fin >> Str;
sL = Str.length();
subL = subStr.length();
fin.close();
}
void search(int i) {
if (hashSubS == hashS) {
if (nr < 1000) {
Sol[nr] = i - subL + 1;
}
nr++;
}
}
void searchEasy(int i) {
if (hashSubS == hashS) {
if (Str.compare(i - subL + 1, subL, subStr) == 0) {
if (nr < 1000) {
Sol[nr] = i - subL + 1;
}
nr++;
}
}
}
void get_Easy_Hash() {
int S = 0;
for (int i = 0; i < subL; i++) {
hashS += Str[i];
hashSubS += subStr[i];
}
search(subL - 1);
for (int i = subL; i < sL; i++) {
hashS = hashS + Str[i] - Str[i - subL];
searchEasy(i);
}
}
void get_Rolling_Hash() {
long long pw = 1;
for (int i = 0; i < subL; i++) {
hashS = (hashS * BASE + Str[i]) % MOD;
hashSubS = (hashSubS * BASE + subStr[i]) % MOD;
if (subL < sL * 7 / 9) {
pw = (pw * BASE) % MOD;
}
}
search(subL - 1);
for (int i = subL; i < sL; i++) {
hashS = ((hashS * BASE + Str[i]) - (pw * Str[i - subL])) % MOD;
if (hashS < 0) {
hashS += MOD;
}
search(i);
}
}
void printSol() {
printf("%d\n", nr);
if (nr > 1000) {
nr = 1000;
}
for (int i = 0; i < nr; i++) {
printf("%d ", Sol[i]);
}
}
int getType() {
if (subL < sL * 7 / 9) {
return RollT;
}
return easyT;
}
int main(){
freopen("strmatch.out", "w", stdout);
read_();
T = getType();
if (T == RollT) {
// 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;
}