x

## 试题 算法提高 Substrings

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.

The first line of the input 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.

There should be one line per test case containing the length of the largest string found.

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

2
2

Tehran 2002 Preliminary

PS： 1. <code class="prism language-csharp">
2. import java.util.Scanner;
3. public class Main {
4. public static void main(String[] args) {
5. Scanner sc=new Scanner(System.in);
6. int a=sc.nextInt();
7. for (int i = 0; i < a; i++) {
8. int n=sc.nextInt();
9. String[]arr=new String[n];
10. String mins="";
11. int len = 101;
12. int index=0;
13. for (int j = 0; j < n; j++) {
14. arr[j]=sc.next();
15. int l = arr[j].length();
16. if (l<len) {
17. len=l;
18. mins=arr[j];
19. index=j;
20. }
21. }
22. for (int j = len; j >=0 ; j--) {
23. boolean f=true;
24. for (int k = 0; k +j<=len ; k++) {
25. boolean flag1=true;
26. boolean flag2=true;
27. //在最短的字符串里面寻找
28. String sub=mins.substring(k,j+k);
29. for (int l = 0; l < n; l++) {
30. if (l==index) {
31. continue;
32. }
33. //没有找到就换成下一个字符串去查
34. if (!arr[l].contains(sub)) {
35. flag1=false;
36. break;
37. }
38. }
39. //当前字符串如果每个都包含的话就可以退出去了
40. if (flag1) {
41. System.out.println(j);
42. f=false;
43. break;
44. }
45. String sub1=new StringBuilder(sub).reverse().toString();
46. for (int l = 0; l < n; l++) {
47. if (l==index) {
48. continue;
49. }
50. if (!arr[l].contains(sub1)) {
51. flag2=false;
52. break;
53. }
54. }
55. if (flag2) {
56. System.out.println(j);
57. f=false;
58. break;
59. }
60. }
61. if (!f) {
62. break;
63. }
64. }
65. }
66. }
67. }
68. </code> 本版积分规则 回帖后跳转到最后一页

462主题 2849积分

### 作者的其他帖子

• 联系我们
• 关注我们
• 社区新手

#### 客服QQ892481490 |小黑屋|手机版|编程之家论坛 ( 桂ICP备18002029号 )