程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> HDU1238

HDU1238

編輯:關於C

簡單的求最大子串問題,難點在於反向比較的也要算
 
[java] 
package D0710; 
 
/*
 * 求子串問題
 * 思路:
 *1、 獲得每組測試數據中最短的字符串
 *2、用最短的字符串的子串進行正相匹配和反向匹配
 *3、得長度最大的子串即可
 * 
 */ 
import java.util.Scanner; 
 
public class HDU1238 { 
 
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
        int t; 
        int n; 
        String[] str;// 保存接收輸入的字符串 
        String[] str2;// 保存str的反串 
        StringBuffer sb; 
        String s;// 保存每組測試數據中最短字符串 
        int len;// 最後得到的最大子串長度 
        t = sc.nextInt(); 
        while (t-- > 0) { 
            n = sc.nextInt(); 
            str = new String[n]; 
            str2 = new String[n]; 
            // 接收輸入 
            for (int i = 0; i < n; i++) { 
                str[i] = sc.next(); 
                sb = new StringBuffer(str[i]); 
                str2[i] = sb.reverse().toString(); 
            } 
            // 得最短字符串, str2中的最短字符串應當和str中一致 
            s = str[0]; 
            for (int i = 0; i < n; i++) { 
                if (str[i].length() < s.length()) { 
                    s = str[i]; 
                    str2[i] = s; 
                } 
            } 
            if (s.equals(str[0])) { 
                str[0] = str2[0] = s; 
            } 
            // 匹配,得最大子串長度 
            len = getLen(s, str, str2); 
            System.out.println(len); 
        } 
 
    } 
 
    private static int getLen(String s, String[] str, String[] str2) { 
 
        int l = str.length; 
        boolean flag = false; 
        int l2 = s.length(); 
        String sub;// 子串 
        String rsub = "";// 最後的子串 
        int i, j, k;// 循環變量 
        for (i = 0; i < l2; i++) { 
            for (j = i + 1; j <= l2; j++) { 
                sub = s.substring(i, j); 
                // 正向匹配 
                for (k = 0; k < l; k++) { 
                    if (str[k].contains(sub)) { 
                        flag = true; 
                    } else { 
                        flag = false; 
                        break; 
                    } 
                } 
                if (flag) { 
                    if (sub.length() > rsub.length()) 
                        rsub = sub; 
                } 
                // 反向匹配 
                for (k = 0; k < l; k++) { 
                    if ( str2[k].contains(sub)) { 
                        flag = true; 
                    } else { 
                        flag = false; 
                        break; 
                    } 
                } 
                if (flag) { 
                    if (sub.length() > rsub.length()) 
                        rsub = sub; 
                } 
            } 
        } 
        //System.out.println(rsub); 
        return rsub.length(); 
    } 
 

 作者:lhfight

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved