现在的位置: 首页 > 综合 > 正文

1387 最长重复子串

2012年09月18日 ⁄ 综合 ⁄ 共 877字 ⁄ 字号 评论关闭
描述

对于一个字符串S1,其中S2是他的一个子串(长度严格小于S1长度),如果S2在S1中出现次数超过1次,那么S2就是一个重复子串,现在的要求是给定S1,请求出他的最长重复子串;

如果有多个长度一样的最长子串,请输入字典序最小那个串;

比如bbbaaaccc

那么最长子串就是aa

输入

第一行包含一个整数T,表示有T组数据

对于每组数据包含一行,该行有一个字符串,长度小于10,000

输出

对于每组数据请输出他的最长重复子串,保证每组数据都有;

样例输入
2
abacabac
abacabbac
样例输出
abac

bac

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

#define MAXCHAR 10010 

char c[MAXCHAR], *a[MAXCHAR];

int comlen( char *p, char *q )
{
	int i = 0;

	while( *p && (*p++ == *q++) )
	{
		++i;
	}
	return i;
}

int pstrcmp( const void *p1, const void *p2 )
{
	return strcmp( *(char* const *)p1, *(char* const*)p2 );
}

int main( )
{
	char ch;
	int n=0;
	int i, temp;
	int maxlen=0, maxi=0;
	int number,t;

	scanf("%d",&number);
	
	getchar();
	
	for(t=1;t<=number;t++)
	{
		n=0;
		maxlen=0;
		maxi=0;
		while( (ch=getchar())!='\n' )
		{
			a[n]=&c[n];
			c[n++]=ch;
		}
		c[n]='\0';
		
		qsort( a, n, sizeof(char*), pstrcmp );

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

	//system("PAUSE");

	return 0;
}

抱歉!评论已关闭.