最长公共字符串

Posted on

题目描述

1
计算两个字符串的最大公共字串的长度，字符不区分大小写

输入描述

1
输入两个字符串

输出描述

1
输出一个整数

示例

输入

1
2
asdfas
werasdfaswer

输出

1
6
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
package main
import "fmt"
import "strings"

func main() {
    for {
        var m, n string
        if _, err := fmt.Scan(&m); err != nil {
            return
        }
        
        if _, err := fmt.Scan(&n); err != nil {
            return
        }
        
       
        m = strings.ToLower(m)
        n = strings.ToLower(n)
        
        var max int
        var dp [][]int = make([][]int, len(m)+1)
        for i := range dp {
            dp[i] = make([]int, len(n)+1)
        }
        
        for i := 1; i <= len(m); i++ {
            for j := 1; j <= len(n); j++ {
                if m[i-1] == n[j-1] {
                    dp[i][j] = dp[i-1][j-1] + 1
                }
                
                if dp[i][j] > max {
                    max = dp[i][j]
                }
            }

        }
        
        fmt.Println(max)
    }
}
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
package main
import "fmt"
import "strings"

func main() {
    for {
        var m, n string
        if _, err := fmt.Scan(&m); err != nil {
            return
        }

        if _, err := fmt.Scan(&n); err != nil {
            return
        }



        var longStr, shortStr string
        if len(m) >= len(n) {
            longStr = strings.ToLower(m)
            shortStr = strings.ToLower(n)
        } else {
            shortStr = strings.ToLower(m)
            longStr = strings.ToLower(n)
        }

        var maxLen int
        for i := 0; i < len(shortStr); i++ {
            for j := 1; j <= len(shortStr) - i; j++ {
                if strings.Contains(longStr, shortStr[i:i+j]) {
                    if maxLen < j {
                        maxLen = j
                    }
                }
            }

        }

        fmt.Println(maxLen)
    }
}