2. 如果不想用递归，可以考虑另外一种思路是
对于t，可以看成被一些*串（连续的*组成的子串）划分成了一组跟s一样纯由字母组成的子串。
这样问题就转化成了在s中寻找一个子串序列。
- 开始时还像普通的串匹配一样，移动s和t，直到t遇到第一个*
- 然后t后面的部分假设被*串划分成如下一组字符字串：t1, t2, t3
- 那么问题变成了从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 |
}
|