zoj 1374 & & 2784 & & 2907 문자열 검색

kmp 를 말 하지 않 으 면 세 문 제 는 모두 물 문제 라 고 할 수 있 습 니 다. kmp 에서 데이터 구 조 를 배 웠 지만 연구 한 적 이 없어 서 잘 모 릅 니 다.이 세 문 제 는 모두 하나의 유형 으로 1374 만 말 하고 다른 두 문 제 는 모두 간략화 판 이 며 유일한 어 려 운 점 은 출력 이 사전 순서에 따라 야 한 다 는 것 이다.당분간 kmp 보고 싶 지 않 아 요.
zoj 1374 Substrings 제목:
 
n 개의 문자열 을 보 여 줍 니 다. 그 중에서 가장 긴 문자열 을 찾 아야 합 니 다. 정반 대도 좋 습 니 다.
 
분석:
그 중에서 가장 짧 은 문자열 을 찾 은 다음 에 열 거 된 하위 문자열 을 찾 은 다음 에 모든 문자열 에서 찾 습 니 다.
강력 한 strstr 함수:
strstr(char *haystack,char *needle) :
문자열 haystack 에서 needle 이 처음 나타 난 위 치 를 찾 습 니 다.

#include<stdio.h>
#include<string.h>
int main()
{
	char str[105][105],up[105],back[105];
	int t,n,i,j,k,min,temp,len,num;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		min=999;
		for(i=0;i<n;i++)
		{
			scanf("%s",str[i]);
			len=strlen(str[i]);
			if(min>len)
			{
				min=len;
				temp=i;
			}
		}
		for(i=1;i<=min;i++)//i         ....
		{
			for(j=0;j+i-1<min;j++)//j+i-1        ,j   
			{
				for(k=0;k<i;k++)//     
				{
					up[k]=str[temp][k+j];
					back[k]=str[temp][i+j-k-1];//            。
				}
				up[k]='\0';
				back[k]='\0';//      ，          
				for(k=0;k<n;k++)//  ，strstr       
				{
					if(strstr(str[k],up)==NULL&&strstr(str[k],back)==NULL)
						break;
				}
				if(k>=n)
				{
					num=i;
				}
			}
		}
		printf("%d
",num);
	}
	return 0;
}

zoj 2784 blue jeans 작년 학교 경기 제목

#include<stdio.h>
#include <string.h>
int main()
{
	int n,m;
	char str[12][62],a[62],b[62];
	int i,j,len,num,tmp,k,t;
	scanf("%d",&n);
	while(n--)
	{
		num=0;
		scanf("%d",&m);
		for(i=0;i<m;i++)
			scanf("%s",str[i]);
		len=strlen(str[0]);
		for(i=1;i<=len;i++)
		{
			for(j=0;j+i-1<len;j++)
			{
				for(k=0;k<i;k++)
				{
					a[k]=str[0][j+k];
				}
				a[k]='\0';
				for(k=0;k<m;k++)
				{
					if(strstr(str[k],a)==NULL)
						break;
				}
				if(k>=m)
				{
					tmp=strlen(a);		
					if(tmp==num)
					{
						for(t=0;t<num;t++)
						{
							if(a[t]<b[t]) 
							{
								for(t=0;t<=num;t++)
									b[t]=a[t];
								break;
							}
						}
					}
					if(tmp>num)
					{
						num=tmp;
						for(t=0;t<=num;t++)
						{
							b[t]=a[t];
						}
					}

				}
			}
		}
		if(num>=3)
		printf("%s
",b);
		else printf("no significant commonalities
");
	}
	return 0;
}

zoj 2907 Corporate Identity,==b
많 지 않 은 문제.폭력 을 끝까지!!!

#include<stdio.h>
#include <string.h>
int main()
{
	int m;
	char str[4005][205],a[205],b[205];
	int i,j,len,num,tmp,k,t,l1=255,pos;
	while(scanf("%d",&m)!=EOF)
	{
		num=0;
		l1=255;
		if(m==0) break;
		for(i=0;i<m;i++)
		{
			scanf("%s",str[i]);
			len=strlen(str[i]);
			if(len<l1)
			{
				l1=len;
				pos=i;
			}
		}
		for(i=1;i<=l1;i++)
		{
			for(j=0;j+i-1<l1;j++)
			{
				for(k=0;k<i;k++)
				{
					a[k]=str[pos][j+k];
				}
				a[k]='\0';
				for(k=0;k<m;k++)
				{
					if(strstr(str[k],a)==NULL)	break;
				}
				if(k>=m)
				{
					tmp=strlen(a);
					if(tmp==num)
					{
						for(t=0;t<num;t++)
						{
							if(a[t]>b[t]) break;
							if(a[t]<b[t]) 
							{
								for(t=0;t<=num;t++)
									b[t]=a[t];
								break;
							}
						}
					}
					if(tmp>num)
					{
						num=tmp;
						for(t=0;t<=num;t++)
						{
							b[t]=a[t];
						}
					}
				}
			}
		}
		if(num>=1)
		printf("%s
",b);
		else printf("IDENTITY LOST
");
	}
	return 0;
}

/*
3
abcclaab
abccdaab
abcckaab
*/
/*
3
asdsaaa
sdswssaaa
sdsaaa
*/