Tag Archives: KMP

LeetCode Add Bold Tag in String

LeetCode Add Bold Tag in String
Given a string s and a list of strings dict, you need to add a closed pair of bold tag <b> and </b> to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.
Example 1:

Input:
s = "abcxyz123"
dict = ["abc","123"]
Output:
"<b>abc</b>xyz<b>123</b>"

Example 2:

Input:
s = "aaabbcc"
dict = ["aaa","aab","bc"]
Output:
"<b>aaabbc</b>c"

Note:

  1. The given dict won't contain duplicates, and its length won't exceed 100.
  2. All the strings in input have length in range [1, 1000].

给定一个字符串s和一个字典dict,如果dict中的单词是s的子串,则要对这个子串加<b></b>的标签。如果有多个重叠的子串都需要加标签,则这些标签需要合并。比如样例2中,子串aaa、aab和bc重叠了,则他们的标签合并,最终结果就是<b>aaabbc</b>c。
这一题其实比第三题要简单。
因为有多个子串可能重叠,为了方便,设置一个长度和s一样的数组flag,flag[i]=1表示第i位需要被标签包围,flag[i]=0表示不需要被标签包围。
把dict中的每个字符串,去s中找,判断是否是s的子串,如果是,则把子串对应的flag位置1。当dict中的所有字符串都查完了。最后遍历flag,把连续1对应的子串加上标签就好了。
这里字符串匹配查找我直接用stl的find,自己写kmp也是可以的。完整代码如下:

class Solution {
public:
	string addBoldTag(string s, vector<string>& dict) {
		int n = s.size();
		string flag(n, '0');
		for (const auto& sub : dict) {
			size_t pos = s.find(sub, 0);
			while (pos != string::npos) {
				fill(flag.begin() + pos, flag.begin() + pos + sub.size(), '1');
				pos = s.find(sub, pos + 1);
			}
		}
		string ans = "";
		int i = 0, j = 0;
		while (flag[i] == '0')++i;
		ans += s.substr(0, i);
		while (i < n) {
			int j = i + 1;
			while (j < n&&flag[j] == '1')++j;
			ans += "<b>" + s.substr(i, j - i) + "</b>";
			if (j >= n)break;
			i = j;
			while (j < n&&flag[j] == '0')++j;
			ans += s.substr(i, j - i);
			i = j;
		}
		return ans;
	}
};

本代码提交AC,用时22MS。

LeetCode Implement strStr()

LeetCode Implement strStr()
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.


串的模式匹配问题,首先献上暴力方法:

class Solution {
public:
	int strStr(string haystack, string needle) {
		int n1 = haystack.size(), n2 = needle.size();
		if (n2 > n1)return -1;
		for (int i = 0; i < n1 - n2 + 1; i++) {
			bool found = true;
			for (int j = 0; j < n2; j++) {
				if (needle[j] != haystack[i + j]) {
					found = false;
					break;
				}
			}
			if (found)return i;
		}
		return -1;
	}
};

本代码提交AC了,用时6MS。
然后使用神器KMP算法,如下:

class Solution {
public:
	void getNextVal(vector<int>& nextval, string t) {
		int n = t.size();
		nextval.resize(n);
		nextval[0] = -1;
		int j = 0, k = -1;
		while (j < n - 1) {
			if (k == -1 || t[j] == t[k]) {
				j++;
				k++;
				if (t[j] != t[k])
					nextval[j] = k;
				else
					nextval[j] = nextval[k];
			}
			else
				k = nextval[k];
		}
	}
	int strStr(string haystack, string needle) {
		if (needle == "")return 0;
		int n1 = haystack.size(), n2 = needle.size();
		if (n2 > n1)return -1;
		vector<int> nextval;
		getNextVal(nextval, needle);
		int i = 0, j = 0;
		while (i < n1&&j < n2) {
			if (j == -1 || haystack[i] == needle[j]) {
				i++;
				j++;
			}
			else
				j = nextval[j];
		}
		if (j >= n2)
			return i - n2;
		else
			return -1;
	}
};

本代码提交AC,用时4MS。


下面还是仔细回顾一下KMP算法,免得以后忘了不好学。
假设主串为s,模式串为t,暴力的方法是依次检查以s[i]开头能否和t匹配成功,如果匹配不成功,则从s的下一个位置s[i+1]开始重新匹配。
但是如果遇到下图的情况:

很显然,从s的下一个位置'B'开始和t的开头重新匹配时,一定会失败,因为之前匹配的串是"ABCDAB",要想再次成功匹配,可以把AB的前缀移到AB后缀的地方,也就是指向主串的i指针不变,j指针指向'C'重新开始下一轮匹配。

那么怎样才能知道此时应该j指针应该调整到指向'C'呢?KMP算法的关键就是计算next数组了,next数组的作用就是当s[i]和t[j]失配时,i指针不动,j指针调整为next[j]继续匹配。
通过上面两张图的例子,我们知道next[j]的含义就是在t[j]之前的串中,相同的前缀和后缀的最大长度。比如上图匹配到ABCDABD时失配,此时j指向最后一个字母'D','D'之前的串ABCDAB中最长的相同的前缀后缀是'AB',所以next[j]=2,下一次,我们令j=next[j]=2,这样就直接从t[j]=t[2]='C'开始匹配了。
(t[0,...,j]的前缀要以t[0]开头,后缀要以t[j]结尾,但都不能完全等于t[0,...,j],即前缀不能以t[j]结尾,后缀不能以t[0]开头。)

next[j]=\begin{cases} \max\{k|0<k<j|t_0t_1...t_{k-1}==t_{j-k}t_{j-k+1}...t_{j-1}\}, & \mbox{if this set is nonempty}\\-1, & \mbox{if }j==0\\ 0, & \mbox{otherwise}\end{cases}


既然next[j]的含义就是在t[j]之前的串中,相同的前缀和后缀的最大长度。假设我们已经知道next[0,...,j]了,怎样求解next[j+1]呢?
假设next[j]=k,说明t[0,...,j-1]最长的相同前缀后缀长度为k。
如果t[j]==t[k],则t[0,...,j]的最长的相同前缀后缀长度就是k+1了,即next[j+1]=k+1,这个很好理解。

如果t[j]!=t[k],则以t[j]结尾的长度为k的后缀就没戏了,因为t[0,...,k]!=t[j-k,...,j],但是后缀又必须以t[j]结尾,所以我们只能缩短长度,从next[k]处继续递归往前查找。即k=next[k]递归查找,注意,递归时j不变,只是k往前递归。
常规的next数组求解就是这样的,但是有一个地方还可以改进,下面引用july的博客:
比如,如果用之前的next 数组方法求模式串“abab”的next 数组,可得其next 数组为-1 0 0 1(0 0 1 2整体右移一位,初值赋为-1),当它跟下图中的文本串去匹配的时候,发现b跟c失配,于是模式串右移j - next[j] = 3 - 1 =2位。

右移2位后,b又跟c失配。事实上,因为在上一步的匹配中,已经得知t[3] = b,与s[3] = c失配,而右移两位之后,让t[ next[3] ] = t[1] = b 再跟s[3]匹配时,必然失配。问题出在哪呢?

问题出在不该出现t[j] = t[ next[j] ]。为什么呢?理由是:当t[j] != s[i] 时,下次匹配必然是t[ next [j]] 跟s[i]匹配,如果t[j] = t[ next[j] ],必然导致后一步匹配失败(因为t[j]已经跟s[i]失配,然后你还用跟t[j]等同的值t[next[j]]去跟s[i]匹配,很显然,必然失配),所以不能允许t[j] = t[ next[j ]]。如果出现了t[j] = t[ next[j] ]咋办呢?如果出现了,则需要再次递归,即令next[j] = next[ next[j] ]。
所以,咱们得修改下求next 数组的代码。

//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1)
	{
		//p[k]表示前缀,p[j]表示后缀
		if (k == -1 || p[j] == p[k])
		{
			++j;
			++k;
			//较之前next数组求法,改动在下面4行
			if (p[j] != p[k])
				next[j] = k;   //之前只有这一行
			else
				//因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
				next[j] = next[k];
		}
		else
		{
			k = next[k];
		}
	}
}

得到next数组就好办了,一旦t[j]!=s[i]失配,i不动,j=next[j]继续匹配。

hihoCoder 1015-KMP算法

hihoCoder 1015-KMP算法
#1015 : KMP算法
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho是一对好朋友,出生在信息化社会的他们对编程产生了莫大的兴趣,他们约定好互相帮助,在编程的学习道路上一同前进。
这一天,他们遇到了一只河蟹,于是河蟹就向小Hi和小Ho提出了那个经典的问题:“小Hi和小Ho,你们能不能够判断一段文字(原串)里面是不是存在那么一些……特殊……的文字(模式串)?”
小Hi和小Ho仔细思考了一下,觉得只能想到很简单的做法,但是又觉得既然河蟹先生这么说了,就肯定不会这么容易的让他们回答了,于是他们只能说道:“抱歉,河蟹先生,我们只能想到时间复杂度为(文本长度 * 特殊文字总长度)的方法,即对于每个模式串分开判断,然后依次枚举起始位置并检查是否能够匹配,但是这不是您想要的方法是吧?”
河蟹点了点头,说道:”看来你们的水平还有待提高,这样吧,如果我说只有一个特殊文字,你能不能做到呢?“
小Ho这时候还有点晕晕乎乎的,但是小Hi很快开口道:”我知道!这就是一个很经典的模式匹配问题!可以使用KMP算法进行求解!“
河蟹满意的点了点头,对小Hi说道:”既然你知道就好办了,你去把小Ho教会,下周我有重要的任务交给你们!“
”保证完成任务!”小Hi点头道。
提示一:KMP的思路
提示二:NEXT数组的使用
提示三:如何求解NEXT数组
输入
第一行一个整数N,表示测试数据组数。
接下来的N*2行,每两行表示一个测试数据。在每一个测试数据中,第一行为模式串,由不超过10^4个大写字母组成,第二行为原串,由不超过10^6个大写字母组成。
其中N<=20
输出
对于每一个测试数据,按照它们在输入中出现的顺序输出一行Ans,表示模式串在原串中出现的次数。
样例输入
5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD
样例输出
3
1
3
1


题目大意就是用KMP算法求解一个子串在主串中出现的次数。我们都知道常规KMP算法可以用来判断一个模式串t是否在主串s中出现过,以及出现的位置。但是这题要求我们求出出现的次数。我们只需要对KMP算法稍加修改即可。
KMP的详细介绍可以看这里,我是仔细看了学校发的李春葆版本《数据结构》P105,代码也基本上照搬课本,使用的是修正后的求nextval数组的KMP算法。具体代码如下:

#include<iostream>
#include<string>
using namespace std;
int nextval[10001];
//改进的next数组求法
void get_nextval(const string &t)
{
	int j=0,k=-1;
	nextval[0]=-1;
	int t_len=t.size();
	while(j<t_len)
	{
		//t[k]表示前缀,t[j]表示后缀
		if(k==-1||t[j]==t[k])
		{
			j++;
			k++;
			//较之前next数组求法,改动在下面4行
			if(t[j]!=t[k])
				nextval[j]=k;  //之前只有这一行
			else
				nextval[j]=nextval[k]; // 继续递归
		}
		else
			k=nextval[k]; // 递归往前找
	}
}
//t为模式串,s为主串;返回t在s中出现的次数
int get_show_times_kmp(const string &t,const string &s)
{
	int t_len=t.size(),s_len=s.size(),i=0,j=0;
	int times=0;
	//int *nextval=new int[t_len];
	get_nextval(t);
	while(i<s_len)
	{
		if(j==-1||s[i]==t[j])
		{
			i++;
			j++;
		}
		else
			j=nextval[j];
		if(j==t_len)
		{
			times++;
			//i=i-t_len+1;
			//j=0;//如果匹配成功的话,无需从t的开头重新匹配,也是只要将t右滑j-k个位置。看《数据结构》P107
		}
	}
	return times;
}
int main()
{
	int n;
	string t,s;//t为模式串,s为主串
	cin>>n;
	while(n--)
	{
		cin>>t>>s;
		cout<<get_show_times_kmp(t,s)<<endl;
	}
	return 0;
}

我做的修改只有一处,就是KMP搜索的时候,如果j==t_len说明在主串s中找到了一个t的匹配,令times++,此时程序还不能结束,我们要让匹配继续下去,为了让while成立,修改while条件只有i<s_len。
其实这个思路是我后来看某大神的解法思考过后才想明白的。我最开始的想法是这样的:既然在t.j和s.i处匹配成功,要进行下一轮匹配时,就应该令j=0,i=i-t_len+1;,也就是从主串s匹配成功起始位置的下一个位置和模式串t的起始位置开始重新匹配。这样做虽然正确,但是TLE超时。后来我仔细看课本P107图4.10,假设t=t_0t_j ,且t_j==s_i,因为t_0...t_{k-1}==t_{j-k}...t_{j-1},所以如果要进行下一次匹配,也可以直接将t_0...t_{k-1}右滑到t_{j-k}...t_{j-1}的位置,也就是t_0...t_{k-1}==s_{i-k}...s_{i-1},再依次判断s_i是否等于t_k。这其实就是令j=nextval[j]。所以当j==t_len的时候,不需要特别处理,直接下一次循环就好。这样可以节省很多时间。
以上代码在hiho中AC,用时226ms,内存7MB。