Pagini recente » Cod sursa (job #3195209) | Cod sursa (job #1649955) | Cod sursa (job #2411186) | Cod sursa (job #1981654) | Cod sursa (job #768218)
Cod sursa(job #768218)
#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 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;
}
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 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();
printSol();
return 0;
}