首页 > 代码库 > ACM-字符串处理之Substrings——hdu1238
ACM-字符串处理之Substrings——hdu1238
Substrings
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6823 Accepted Submission(s): 3053
Problem Description
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.
Input
The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.
Output
There should be one line per test case containing the length of the largest string found.
Sample Input
2 3 ABCD BCDFF BRCD 2 rose orchid
Sample Output
2 2
Author
Asia 2002, Tehran (Iran), Preliminary
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1238
这道题目,可以用搜索来做。
我用的时string.h几个函数。
strcpy:
char * strcpy(char * strDest,const char * strSrc);
就是将后面的数组赋给前面。如果前面数组长度不够大,运行崩溃。
strncpy:
char
*
strncpy
(
char
*dest,
char
*src,size_tnum);
这个与strcpy差别在于,它可以控制长度,当然这两者都可以通过控制 第二个数组的头位置来控制赋值起点。
strlen:
extern unsigned int strlen(char *s);
这个就是返回s数组长度(不包括‘\0‘)
strstr:
extern char *strstr(const char *str1, const char *str2);
这个函数就是查找str2在str1中的位置,若不存在返回NULL。
仅这四个函数,即可解这道题。
/************************************** *************************************** * Author:Tree * *From :http://blog.csdn.net/lttree * * Title : Substrings * *Source: hdu 1238 * * Hint : 串的处理 * *************************************** **************************************/ #include <stdio.h> #include <string.h> char str[101][101]; int n; int find_str(int len,int index) { char s[101],pos[101],inv[101]; bool flag; int i,j,l; //将字符串拷贝出来 strcpy(s,str[index]); l=len; // 舍弃后面的 while(l>0) { flag = 0; for(i = 0; i <= len-l; ++i) { flag=1;//flag初始化为1 //正向字符串,将str中第i个位置,取l长度(舍弃前面的) strncpy(pos,s+i,l); //inv 为pos的逆序 for(j=0; j<l; j++) inv[j]=pos[l-j-1]; // 字符数组,最后\0,防止某些不必要的冲突 pos[l]=inv[l] =‘\0‘; for(j=0; j<n; j++) { if(strstr(str[j],pos)==NULL&&strstr(str[j],inv)==NULL) {flag=0;break;} } if(flag) break; } if(flag) break; --l; } return l; } int main() { int i,t,min_len,index; scanf("%d",&t); while(t--) { scanf("%d",&n); min_len = 101; for(i = 0; i < n; i++) { scanf("%s",str[i]); //找到最短的字符串 if(strlen(str[i])<min_len) { min_len = strlen(str[i]);//记录最短字串的长度 index = i;//记录最短字串的位置 } } printf("%d\n",find_str(min_len,index)); } return 0; }
ACM-字符串处理之Substrings——hdu1238
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。