Platinum Partner

Find The Longest Duplicated Substring In C

The programme finds the longest substring that is duplicated.


#include 
#include 
#include 

#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;
}

{{ tag }}, {{tag}},

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}
{{ parent.authors[0].realName || parent.author}}

{{ parent.authors[0].tagline || parent.tagline }}

{{ parent.views }} ViewsClicks
Tweet

{{parent.nComments}}