Pagini recente » Cod sursa (job #1600251) | Cod sursa (job #1103135) | Cod sursa (job #779198) | Cod sursa (job #2378920) | Cod sursa (job #768146)
Cod sursa(job #768146)
#include <stdio.h>
#include <string>
#include <fstream>
using namespace std;
string Str, subStr;
int sL, subL;
int hash[2000000], hashS;
int nr, Sol[2000000];
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 (Str.compare(i - subL + 1, subL, subStr) == 0) {
Sol[nr++] = i - subL + 1;
}
}
}
}
void printHash(){
for (int i = 0; i < sL; i++) {
printf("%c %d; ", Str[i], hash[i]);
}
printf("\n%d\n\n", hashS);
}
void get_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];
}
//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;
}