DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Find The Longest Duplicated Substring In C

11.16.2008
| 5799 views |
  • submit to reddit
        The programme finds the longest substring that is duplicated.

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

#define MAXN 5000000

int n;
char c[MAXN], *a[MAXN];

int pstrcmp(const void **x, const void **y) {
	return strcmp(*(char**)x, *(char**)y);
}

int comlen(char *p, char *q) {
	int i = 0;
	while (*p && (*p++ == *q++))
		++i;
	return i;
}

int main(int argc, char *argv[]) {
	int i;
	FILE *fi = fopen("james.txt", "r");
	char ch;
	while (fread(&ch, 1, 1, fi)) {
		a[n] = &c[n];
		c[n++] = ch;
	}
	c[n] = 0;
	fclose(fi);

	qsort(a, n, sizeof(char*), pstrcmp);

	int maxlen = 0, maxi = 0;
	for (i = 0; i < n-1; ++i)
		if (comlen(a[i], a[i+1]) > maxlen) {
			maxlen = comlen(a[i], a[i+1]);
			maxi = i;
		}
	
	printf("%.*s\n", maxlen, a[maxi]);

	return 0;
}