Pagini recente » Cod sursa (job #572378) | Cod sursa (job #2639778) | Cod sursa (job #1931886) | Cod sursa (job #2165140) | Cod sursa (job #2794699)
#include <cstdio>
#include <cstring>
#define MAX 2000000
using namespace std;
char strA [MAX], strB[MAX];
int i, Hash, fHash, j, cntPoz, check;
int Poz [1000];
int compute (char v[], int length){
int y, hash;
y = hash = 0;
while (y < length){
hash += v[y];
y ++;
}
return hash;
}
int addHash (char c, int var){
return var + (int) c;
}
int removeHash (char c, int var){
return var - (int) c;
}
int checkString (int a, int h){
int l;
l = 0;
while (l <= h){
if (strB[a + l - 1] != strA [l])
return 1;
l ++;
}
return 0;
}
int main() {
FILE *in, *out;
in = fopen("strmatch.in", "r");
out = fopen("strmatch.out", "w");
i --; // calc valoarea hash-ului stringului A
while (strA[i] != '\n'){
check = fgetc(in);
strA [++i] = check;
Hash = addHash (strA[i], Hash);
}
Hash -= 10;
i --;
//calc valoarea hash-ului primelor i charactere unde i este lungimea primului Hash
for (j = 0; j <= i; j ++)
strB [j] = fgetc (in);
fHash = compute (strB, j);
//LastPos indica unde se afla in StrB ultimul character al hash-ului
int LastPos = 0;
while (((strB[j - 1] >= 'A' && strB[j - 1] <= 'Z')||(strB[j - 1] >= 'a' && strB[j - 1] <= 'z'))&&cntPoz < 1000){
//verific egalitatea hash-urilor
if (fHash == Hash ){
//numai dupa acea verific egalitatea stringurilor
if (!checkString(j - i, i)) {
Poz[cntPoz] = LastPos;
cntPoz ++;
}
}
//scot ultimul numar din hash si adaug primul element din strB
fHash = removeHash (strB[LastPos], fHash);
strB [j] = fgetc (in);
j ++;
fHash = addHash (strB[j - 1], fHash);
LastPos ++;
}
//afisez rezultatele
fprintf (out, "%d\n", cntPoz);
for (int k = 0; k < cntPoz; k ++)
fprintf (out, "%d ", Poz[k]);
return 0;
}