Fork me on GitHub

枚举法

发表于 | 更新于 | 分类于

基本思想

  • 枚举也称作穷举，指的是从问题所有可能的解的集合中一一枚举各元素。
  • 用题目中给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立。即为其解。

例题：最长公共连续子串

牛牛有两个字符串（可能包含空格）,牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。

输入描述:
1
输入为两行字符串（可能包含空格），长度均小于等于50.
输出描述:
1
输出为一个整数，表示最长公共连续子串的长度。

解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

import java.util.Scanner;
 
public class Main
{
     
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        scanner.close();
         
        //字符串的长度
        int n1 = str1.length();
        int n2 = str2.length();
         
        //边界情况
        if(n1 < 1 || n2 < 1)
        {
            System.out.println(0);
            return;
        }
        //利用空间存储两个串的比较结果，空间换时间
        int temp[][] = new int[n1][n2];
        //表示最长的公共字串的变量
        int longest = 0;
        char[] char1 = str1.toCharArray();
        char[] char2 = str2.toCharArray();
         
        //初始化数组temp
        for(int i = 0; i < n1; i++)
        {
            for(int j = 0;j <n2;j++)
            {
                temp[i][j] = 0;
            }
        }
         
        //初始化第一行，初始化第一列，因为状态转移公式：item[i][j]=1 +item[i-1][j-1]
        for(int i = 0;i < n1;i++)
        {
            if(char1[i] == char2[0])
                temp[i][0] = 1;
        }
         
        for(int i = 0;i < n2;i++)
        {
            if(char1[0] == char2[i])
                temp[0][i] = 1;
        }
         
         
        //利用状态转移方程进行填充temp二维数组
        for(int i = 1; i < n1;i++)
        {
            for(int j = 1; j<n2;j++)
            {
                if (char1[i] == char2[j])
                {
                    temp[i][j] = temp[i-1][j-1] +1;
                }
            }
        }
         
        for(int i = 0; i < n1;i++)
        {
            for(int j = 0; j<n2;j++)
            {
                if(temp[i][j] > longest)
                    longest = temp[i][j];
            }
        }
         
        System.out.println(longest);
    }
}