字符串匹配实质:树上或图中,点与点或连通块与连通块,之间的,一一对应关系。
换句话说,字符串匹配的本质是图论。
说在前面——
S:模板串
T:匹配串
n:S长度
m:T长度
常见形式——
1.判断S的子串中是否含有T
子串:S中遵照原序的任意集合,包含空集。
比如S:abcd,那么ad便是S的一个子串。
做法:双指针
时间复杂度:O(min(n,m))
int head = 0, tail = 0, cnt = 0;
while (head < n && tail < m) {if (S[head] == T[tail]) tail++, cnt++;head++;
}
2.判断S的连续子串中是否含有T
连续子串:S中任意一段连续的集合,包含空集。</