Blogs

0%

字符串匹配算法

发表于 更新于 分类于
本文字数： 2.6k 阅读时长 ≈ 4 分钟

刷题的时候遇到的几个与字符串匹配相关的算法。

搜索子字符串

KMP

首先是比较出名的KMP算法

Sunday算法

主要思想：匹配失败的时候关注的是参与匹配的最末位字符的下一个字符。
这个字符如果没有出现在下面字符串里，就直接向右移动字符串长度+1位。
如果出现，就移动字符串长度-出现位置位。
比如，要在substring searching algorithm中搜索algorithm，先从头匹配：

显然不符合，然后直接跳到最末位的下一个，空格没有出现在下面字符串里

不符合，接着找下一个

g出现了，在下标为2的位置，所以右移9-2=7位

显然还是不行，然后再去找下一个，i出现了，在下标5的位置，所以右移4个

经验证符合要求。
java代码如下：

1
public int searchStr(String patternString, String str) {
2
       if (patternString.equals("") || str.equals("")||str.length()>patternString.length())
3
           return -1;
4
       char[] pattern = patternString.toCharArray();
5
       char[] s = str.toCharArray();
6
       int strIndex;
7
       for (int i = 0; i < pattern.length;) {
8
           strIndex = 0;
9
           while (strIndex < s.length) {
10
               if(pattern[i + strIndex] != s[strIndex]) {
11
                   i+=strIndex;
12
                   break;
13
               }
14
               if(strIndex==s.length-1){
15
                   return i;
16
               }
17
               strIndex++;
18
           }
19
           if (i + 1 < pattern.length) {
20
               int charIndex=findChar(s,pattern[i+s.length]);
21
               if(charIndex==-1){
22
                   i+=s.length+1;
23
               }else{
24
                   i+=s.length-charIndex;
25
               }
26
           } else {
27
               return -1;
28
           }
29
       }
30
       return -1;
31
   }
32
   private  int findChar(char[] c,char search){
33
      for(int i=0;i<c.length;i++){
34
          if(c[i]==search)
35
              return i;
36
      }
37
      return  -1;
38
   }

最长回文子串

暴力求解

三层循环，外层遍历字符串，中层遍历子串，三层判定是否回文

中心扩散法

先循环找到相邻且相等的，或者间隔一个且相等两个字符，然后向外扩展找到最长
时间复杂度n²

1
public String longestPalindrome(String s) {
2
        // Write your code here
3
        if (s.equals("") || s.length() == 1)
4
            return s;
5
        char[] result = {};
6
        char[] charArray = s.toCharArray();
7
        for (int i = 0; i < s.length(); i++) {
8
            if (i + 1 < s.length() && charArray[i] == charArray[i + 1]) {
9
                result = result.length <= 2 ? Arrays.copyOfRange(charArray, i, i + 2) : result;
10
                for (int j = 0; j <= s.length() / 2; j++) {
11
                    if (i - j+1 > 0 && i + j + 1 < s.length() && charArray[i - j] == charArray[i + j + 1]) {
12
                        result = result.length < (2 * j + 2) ? Arrays.copyOfRange(charArray, i - j, i + j + 2) : result;
13
                    } else {
14
                        break;
15
                    }
16
                }
17
            }
18
            if (i + 2 < s.length() && charArray[i] == charArray[i + 2]) {
19
                result = result.length <= 3 ? Arrays.copyOfRange(charArray, i, i + 3) : result;
20
                for (int j = 0; j <= s.length() / 2; j++) {
21
                    if (i - j+1 > 0 && i + j + 2 < s.length() && charArray[i - j] == charArray[i + j + 2]) {
22
                        result = result.length < (2 * j + 3) ? Arrays.copyOfRange(charArray, i - j, i + j + 3) : result;
23
                    } else {
24
                        break;
25
                    }
26
                }
27
            }
28
        }
29
        return new String(result);
30
    }

Manacher算法

先对字符串预处理，每个字符中间添加特殊符号比如#
然后引入数组P[i]代表以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]）
S[]ghaweuifhwe123454321fahwu->
S[]#g#h#a#w#e#u#i#f#h#w#e#1#2#1#4#4#1#2#1#f#a#h#w#u#
P[] 1212121212121212121212121412129212141212121212121
可以看出P[i]-1就是原字符串中回文子串的长度，比如12144241中对应的9-1，121对应4-1，所以需要求P[]最大值