文库网
关注排行榜

当前无数据...

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

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:
这道题非常感谢网易词典,规避了我致命的英语

{tilte}-踏雪寻煤

  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>
复制代码

本站资源均由网上搜集或网友上传提供,内容仅供观摩学习交流之用,本站将不对任何资源负法律责任.如有侵犯您的版权,请及时联系我们(邮箱:892481490@qq.com,客服QQ:892481490),我们会尽快处理!QQ350550790是骗子,注意不要和他交易!!!
发帖求助前要善用【论坛搜索】功能, 那里可能会有你要找的答案,也能为你节约不少学习时间;
如何回报帮助你解决问题的坛友,好办法就是点击帖子下方的评分按钮给对方加(威望)和(贡献)而不会扣除自己的积分。
如发现灌水帖、病毒木马帖、广告帖、工具不能正常使用、网盘链接失效,请点击【举报】 核实有几率会给予额外的B币奖励哦!
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    发布资源 快速回复 返回列表 客服中心 官方QQ群

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

    Powered by 编程之家  © 20019-2021