Pagini recente » Cod sursa (job #691588) | Cod sursa (job #377061) | Profil mariejeanne | Cod sursa (job #3132755) | Cod sursa (job #2086430)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STRINGLENGTH 2000002
#define PATTERNLENGTH 2000002
#define TRUE 1
#define FALSE 0
#define BASE 3
#define PRIME 101
typedef char* string;
typedef size_t bool;
char text[STRINGLENGTH];
char pattern[PATTERNLENGTH];
size_t out[PATTERNLENGTH];
static inline __attribute__((always_inline))
size_t hash(string text, int pos, int length)
{
size_t S = 0, i;
for (i = pos; i < length + pos; ++i) {
S = (S * BASE + text[i]) % PRIME;
}
return S;
}
int power(int b, int e) {
int ret = 1;
size_t i = 0;
for (i = 0; i < e; i++) {
ret = (ret * b) % PRIME;
}
return ret;
}
int main(int argc, char** argv)
{
size_t strlens;
size_t strlenp;
int output[1000];
size_t i, j, t, match = 0, y = 0;
if (freopen("strmatch.in", "r", stdin) == NULL) {
return -1;
}
if (fgets(pattern, STRINGLENGTH, stdin) == NULL) {
return -1;
}
strlenp = strlen(pattern);
if (pattern[strlenp - 1] == '\n') {
pattern[strlenp - 1] = '\0';
strlenp--;
}
if (fgets(text, STRINGLENGTH, stdin) == NULL) {
return -1;
}
strlens = strlen(text);
if (text[strlens - 1] == '\n') {
text[strlens - 1] = '\0';
strlens--;
}
/* Calcularea hash-ului primului grup de litere (nu ma pot folosi de
un hash precedent, deoarece calculez pentru prima oara. */
int H = hash(text, 0, strlenp);
/* Calcularea hash-ului pattern-ului */
int hashp = hash(pattern, 0, strlenp);
if (H == hashp) {
int was = TRUE;
for (j = 0; j < strlenp; j++)
{
if (text[i + j] != pattern[j]) {
was = FALSE;
break;
}
}
if (was)
{
if (y < 1000) {
output[y] = i;
y++;
}
match++;
}
was = FALSE;
}
int max_power = power(BASE, strlenp - 1);
for (i = 1; i <= strlens; i++) {
if (i <= strlens) {
H = H - text[i - 1] * max_power;
H = H * BASE;
H = H + text[i + strlenp - 1];
H = H % PRIME;
if (H < 0) H = H + PRIME;
}
if (H == hashp) {
int was = TRUE;
for (j = 0; j < strlenp; j++)
{
if (text[i + j] != pattern[j]) {
was = FALSE;
break;
}
}
if (was)
{
if (y < 1000) {
output[y] = i;
y++;
}
match++;
}
was = FALSE;
}
}
if (freopen("strmatch.out", "w", stdout) == NULL) {
return -1;
}
printf("%d\n", match);
if (match > 1000) {
match = 1000;
}
for (t = 0; t < match; t++) {
printf("%d ", output[t]);
}
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}