代码随想录：字符串
字符串是由若干字符组成的有限序列，可以理解为一个字符数组，处理时定义string类型的变量
KMP算法：主要应用在字符串匹配的场景中，当字符串出现不匹配的情况时可以知道一部分之前匹配的文本内容，利用这些信息去避免从头匹配
next数组是一个前缀表或是前缀表的某种变形
前缀表是用来回退的，它记录了模式串与主串（文本串）不匹配的时候，模式串应该从哪里开始冲重新匹配的信息
前缀表的任务是当前位置匹配失败时，找到之前已经匹配的位置再重新匹配，也意味着在字符串某位置失配时，前缀表会告诉你下一步匹配时模式串应该跳到哪个位置
前缀表记录最长相同前后缀的长度信息
字符串的前缀指不包含最后一个字符的所有以第一个字符开头的连续子字符串，后缀指不包含第一个字符的所有以最后一个字符结尾的连续子字符串
计算前缀表：a最长前后缀长度为0，aa为1，aab为0，aaba为1，aabaa为2，aabaaf为0
上面求得的长度就是前缀表对应元素，模式串aabaaf前缀表即为010120
当文本串和模式串遇到第一个不匹配字符时，寻找前一位下标在前缀表中对应的元素，该元素是多少就跳到下表为多少的位置继续重新匹配
next数组可以是前缀表也可以是前缀表统一减一后得到的前缀表
匹配过程时间复杂度O(n)，建立前缀表时间复杂度O(m)，整个算法时间复杂度O(m+n)比暴力解法O(m*n)效率高很多
力扣344：反转字符串
public class Solution {
public void ReverseString(char[] s) {
for (int i=0, j=(s.Length-1);i<j;i++,j--){
char temp=s[i];
s[i]=s[j];
s[j]=temp;
//双指针不断往中间靠拢交换两头的元素
}
}
}
力扣541：反转字符串II
public class Solution {
public string ReverseStr(string s, int k)
{
char[] chars = s.ToCharArray();
for (int i = 0; i < s.Length; i+=(2*k))
{
//循环寻找每次反转的起点
if (i+k<=s.Length)
{
Array.Reverse(chars,i,k);
continue;
//每次有多于k个字符就反转前k个
}
Array.Reverse(chars,i,s.Length-i);
//少于k个就反转这s.Length-1个字符
}
string ss = new string(chars);
return ss;
//char[]型转换成string作为返回值
}
}
力扣151：反转字符串里的单词
public class Solution {
private string RemoveExtraSpaces(string s)
{
//使用双指针法删除多余的空格，使句子中只保留单词与单词中间的一个空格
int left = 0, right = 0;
StringBuilder ss = new StringBuilder(s);
//将string转换成StringBuilder方便进行操作
while (s.Length>0&& right<s.Length&& ss[right]==' ')
{
right++;
//找到第一个字母的位置
}
for (; right < s.Length; right++)
{
if (right-1>0&& ss[right]==ss[right-1]&& ss[right]==' ')
{
continue;
}
else
{
ss[left] = ss[right];
left ++;
//将句子中的有效信息放在ss的前面
}
}
if (left-1>0&& ss[left-1]==' ')
{
ss.Remove(left - 1,right-left+1);
}
else
{
ss.Remove(left, right - left);
//删除后面的无效信息，分两种情况，一种是最后left-1指向空格则删除left-1后续所有，一种是left-1指向非空格字符则删除left之后所有
}
return ss.ToString();
//返回值为string类型
}
public string ReverseWords(string s)
{
char[] chars=RemoveExtraSpaces(s).ToCharArray();
Array.Reverse(chars);
//删空格，变成字符数组，反转再挨个单词操作
int start = 0, end = 0;
bool entry = false;
for (int i = 0; i < chars.Length; i++)
{
if (!entry|| chars[i]!=' '&& chars[i-1]==' ')
{
start = i;
entry = true;
//每个单词开头一定在空格后面
}
if (entry&& chars[i]==' '&& chars[i-1]!=' ')
{
end = i - 1;
entry = false;
Array.Reverse(chars,start,end-start+1);
//单词结尾后面有空格，将结尾标记在空格前一位然后反转开头到结尾所有字符
}
if (entry&& i==chars.Length-1)
{
end = i;
entry = false;
Array.Reverse(chars,start,end-start+1);
//最后一个单词结尾没有空格，将结尾标记在最后一个字母上然后反转开头到结尾所有字符
}
}
string a = new string(chars);
return a;
}
}
力扣28：找出字符串中第一个匹配字符串的下标
//使用KMP算法，构建next数组，进行匹配节省时间
public class Solution
{
private void GetNext(int[] next, string s)
{
int i = 0;
next[0] = i;
//初始化
for (int j = 1; j < s.Length; j++)
{
while (i>0&& s[i]!=s[j])
{
i = next[i - 1];
//前后缀不相等的情况，这里用while循环不用if判断的原因是前后缀不匹配就要让i循环退到匹配的位置或第0位
}
if (s[i]==s[j])
{
i++;
}
next[j] = i;
//每次循环给j赋值为当前距离第0位的距离即为返回匹配时的开始位置
}
}
public int StrStr(string haystack, string needle) {
if (needle.Length==0)
{
return 0;
}
int[] next = new int[needle.Length];
GetNext(next,needle);
int i = 0;
for (int j = 0; j < haystack.Length; j++)
{
while (i>0&& haystack[j]!=needle[i])
{
i = next[i - 1];
}
if (haystack[j]==needle[i])
{
i++;
}
if (i == needle.Length)
{
return j - needle.Length + 1;
//匹配的上则返回这次匹配的开始位置
}
//这里与制作next数组的原理相同，只是判断是否匹配的地方换成了两个字符串
}
return -1;
}
}
力扣459：重复的子字符串
public class Solution {
private void GetNext(int[] next, string s)
{
int i = 0;
next[0] = i;
for (int j = 1; j < s.Length; j++)
{
while (i>0&& s[i]!=s[j])
{
i = next[i - 1];
}
if (s[i]==s[j])
{
i++;
}
next[j] = i;
//建立next数组的部分与上一题相同
}
}
public bool RepeatedSubstringPattern(string s) {
if(s.Length==0){
return false;
}
int[] next=new int[s.Length];
GetNext(next,s);
if(next[s.Length-1]!=0&&s.Length%(s.Length-next[s.Length-1])==0){
return true;
//难点在于这里如何判断是有循环的，首先若能够有循环最后一位的next数组对应值一定不是0，其次由于前后缀分别不包含头尾元素，最长相等前后缀长度一定是总长度减去进行循环的字符串长度，因此若总长度 能除开 总长度减去最长相等前后缀得到的长度则说明有循环存在，除不开有余数说明不存在循环
}
return false;
}
}
