带通配符*的字符串匹配

时间:2022-01-29 06:26:58

2. 如果不想用递归,可以考虑另外一种思路是

对于t,可以看成被一些*串(连续的*组成的子串)划分成了一组跟s一样纯由字母组成的子串。
这样问题就转化成了在s中寻找一个子串序列。

  1. 开始时还像普通的串匹配一样,移动s和t,直到t遇到第一个*
  2. 然后t后面的部分假设被*串划分成如下一组字符字串:t1, t2, t3
  3. 那么问题变成了从s的当前位置开始找t1,如果没找到,则不匹配;如果找到(这时候有可能s中存在很多t1,我们只需考虑第一个。因为如果第一个能导致整个串匹配成功,则已经达到我们的目的,其他的不用考虑,因为我们并不需要输出所有的匹配。而如果第一个都不能使整个串匹配成功,后面情况由于可供匹配的子串更短,更不可能成功。),则继续从s匹配了t1的部分后面继续找t2;如此操作直至所有的子串都找到时,则整个匹配成功,否则任何一处没匹配则整个匹配失败

为了方便操作,开始时把s和t尾部相等的字符都截掉了。
Java源码:

001 public static boolean isMatch(char[] s, char[] t) {
002         //cut off the tail of non-* characters
003         int i=s.length-1,j=t.length-1;
004         while(i>-1 && j>-1 && s[i] == t[j]) {
005             i--;
006             j--;
007         }
008  
009         int endS = i+1, endT = j+1;
010         i=j=0;
011         while(i<endS && j<endT && s[i] == t[j]) {
012             i++;
013             j++;
014         }
015         if(j==endT) {//t has no *
016             if(i==endS) {//t equals to s
017                 return true;
018             else {
019                 return false;//s is longer than t, unequal
020             }
021         }
022         if(t[j] != '*') {// not match for a non-* character
023             return false;
024         }
025         // the first * is found
026  
027         int subStringStart = j;
028         int subStringEnd = j;
029         while (j < endT) {
030             while (j < endT
031                     && t[j] == '*') {
032                 j++;
033             }
034             if(j==endT) {
035                 return true;
036             }
037             // get the first non-* char
038             subStringStart = j;
039  
040             while (j < endT
041                     && t[j] != '*') {
042                 j++;
043             }
044             // get the last non-* char
045             subStringEnd = j-1;
046  
047             //match it in s using normal string match algorithm
048             i = isNormalMatch(s, i, endS-1, t, subStringStart, subStringEnd);
049             if(i == -1) {
050                 return false;
051             else if(i==endS) {
052                 return true;
053             }
054         }
055  
056         // t ends as a non-* character but s not ends yet
057         return false;
058     }
059  
060     //KMP
061     private static int isNormalMatch(char[] text, int textStart, inttextEnd, char[] pattern, int patternStart, int patternEnd) {
062                 if(textStart>textEnd || patternStart > patternEnd) {
063                     return -1;
064                 }
065         char[] s1 = Arrays.copyOfRange(text, textStart, textEnd+1);
066         char[] s2 = Arrays.copyOfRange(pattern, patternStart, patternEnd+1);
067         int[] next = new int[patternEnd-patternStart+1];
068         caculateNext(s2,next);
069         int i = isMatch(s2,s1,next);
070         if(i != -1) {
071             i = i + textStart + 1;
072         }
073         return i;
074     }
075  
076     private static int isMatch(char[] patternStamp, char[] textStamp, int[] next) {
077         int i = 0, j = 0;
078         while (j < patternStamp.length && i < textStamp.length) {
079             if (j == -1 || patternStamp[j] == textStamp[i]) {
080                 i++;
081                 j++;
082             else {
083                 j = next[j];
084             }
085         }
086  
087         if (j == patternStamp.length) {
088             return i-j;
089         else {
090             return -1;
091         }
092     }
093  
094     private static void caculateNext(char[] pattern, int[] next) {
095         next[0] = -1;
096  
097         int i = 0, j = -1;
098         while(i<pattern.length-1) {
099             if(j==-1 || pattern[i] == pattern[j]) {
100                 i++;
101                 j++;
102                 next[i] = j;
103             else {
104                 j = next[j];
105             }
106         }
107     }