# LeetCode Longest Happy Prefix

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s. Return the longest happy prefix of s .

Return an empty string if no such prefix exists.

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".


Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.


Example 3:

Input: s = "leetcodeleet"
Output: "leet"


Example 4:

Input: s = "a"
Output: ""


Constraints:

• 1 <= s.length <= 10^5
• s contains only lowercase English letters.

class Solution {
public:
string longestPrefix(string s) {
s = s + ".";
int n = s.size();
vector<int> next(n, 0);
next = -1;
int i = 0, j = -1;
while (i < n - 1) {
if (j == -1 || s[i] == s[j]) {
++i;
++j;
next[i] = j;
}
else {
j = next[j];
}
}
return s.substr(0, next[n - 1]);
}
};

# 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].

# LeetCode Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2


Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1


Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

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;
}
};

class Solution {
public:
void getNextVal(vector<int>& nextval, string t)
{
int n = t.size();
nextval.resize(n);
nextval = -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;
}
};

（t[0,…,j]的前缀要以t开头，后缀要以t[j]结尾，但都不能完全等于t[0,…,j]，即前缀不能以t[j]结尾，后缀不能以t开头。）

$$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 数组求法
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next = -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];
}
}
}

class Solution {
public:
vector<int> GetNext(string s) {
int n = s.size();
vector<int> next(n, 0);
next = -1;
int i = 0, j = -1;
while (i < n - 1) {
if (j == -1 || s[i] == s[j]) {
++i;
++j;
next[i] = j;
}
else {
j = next[j];
}
}
return next;
}
int strStr(string haystack, string needle) {
if (needle == "")return 0;
vector<int> next = GetNext(needle);
int m = haystack.size(), n = needle.size();
if (n > m)return -1;
int i = 0, j = 0;
while (i < m&&j < n) {
if (j == -1 || haystack[i] == needle[j]) {
++i;
++j;
}
else {
j = next[j];
}
}
if (j == n)return i - n;
else return -1;
}
};