Skip to content

Instantly share code, notes, and snippets.

@hynekcer
Created January 11, 2018 22:23
Show Gist options
  • Save hynekcer/7e8641998bb57b48c6146fd3640f4fd7 to your computer and use it in GitHub Desktop.
Save hynekcer/7e8641998bb57b48c6146fd3640f4fd7 to your computer and use it in GitHub Desktop.
copy of http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c (with an initial comment)
/* source from
http://stackoverflow.com/questions/13560037/effcient-way-to-find-longest-duplicate-string-for-python-from-programming-pearl
http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c
/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */
/* longdup.c -- Print longest string duplicated M times */
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int pstrcmp(char **p, char **q)
{ return strcmp(*p, *q); }
int comlen(char *p, char *q)
{ int i = 0;
while (*p && (*p++ == *q++))
i++;
return i;
}
#define M 1
#define MAXN 5000000
char c[MAXN], *a[MAXN];
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a[n] = &c[n];
c[n++] = ch;
}
c[n] = 0;
printf("read\n"); //, a[maxi]);
qsort(a, n, sizeof(char *), pstrcmp);
printf("sorted\n"); //, a[maxi]);
for (i = 0; i < n-M; i++)
if (comlen(a[i], a[i+M]) > maxlen) {
maxlen = comlen(a[i], a[i+M]);
maxi = i;
}
printf("%9d\n", maxlen); //, a[maxi]);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment