当前位置: 代码迷 >> 综合 >> 字符串——常见字符串匹配形式
  详细解决方案

字符串——常见字符串匹配形式

热度:58   发布时间:2024-01-16 23:15:46.0

字符串匹配实质:树上或图中,点与点或连通块与连通块,之间的,一一对应关系。

换句话说,字符串匹配的本质是图论。

说在前面——

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中任意一段连续的集合,包含空集。</

  相关解决方案