1. 

*
 * ACM Programming Contest
 * Problem: 902 (Password Search)
 * Status: Accepted
 * Language: ANSI C
 * Runtime: 0.124
 * Date: 2009-05-12 17:17:00
 * Author: Andreas Kunft
 */

#include <stdio.h>
#include <string.h>

#define HASHTABLE_SIZE 9124679
#define BASE 26

int subLength, pIndex;
char str[100000000];
int hashtable[HASHTABLE_SIZE];
unsigned long long save = 0, hash = 0;

long long power(int p) {
long long power = BASE;
for (pIndex = 1; pIndex < p; pIndex++)
power *= BASE;

return power;
}

int main() {
int max = 1;
int pos = 0;
int t, numberOfSubs;
while (scanf("%d %s", &subLength, str) == 2) {

char result[subLength];

memset(hashtable, 0, HASHTABLE_SIZE * sizeof(int));

numberOfSubs = strlen(str) - subLength + 1;

long long saveBase = power(subLength - 1);

int i;
for (i = 0; i < subLength; i++) {
hash += power(subLength - 1 - i) * str[i];
}
save = saveBase * str[0];
hashtable[hash % HASHTABLE_SIZE]++;

for (i = 1; i < numberOfSubs; i++) {
hash = ((hash - save) * BASE) + str[i + subLength - 1];
save = saveBase * str[i];

if ((t = ++hashtable[hash % HASHTABLE_SIZE]) > max) {
max = t;
pos = i;
}
}
memcpy(result, str + pos, subLength);
result[subLength] = '\0';
printf("%s\n", result);
max = pos = save = hash = 0;
}
return 0;
}