代碼隨想錄：字符串
字符串是由若干字符組成的有限序列，可以理解為一個(gè)字符數(shù)組，處理時(shí)定義string類(lèi)型的變量
KMP算法：主要應(yīng)用在字符串匹配的場(chǎng)景中，當(dāng)字符串出現(xiàn)不匹配的情況時(shí)可以知道一部分之前匹配的文本內(nèi)容，利用這些信息去避免從頭匹配
next數(shù)組是一個(gè)前綴表或是前綴表的某種變形
前綴表是用來(lái)回退的，它記錄了模式串與主串（文本串）不匹配的時(shí)候，模式串應(yīng)該從哪里開(kāi)始沖重新匹配的信息
前綴表的任務(wù)是當(dāng)前位置匹配失敗時(shí)，找到之前已經(jīng)匹配的位置再重新匹配，也意味著在字符串某位置失配時(shí)，前綴表會(huì)告訴你下一步匹配時(shí)模式串應(yīng)該跳到哪個(gè)位置
前綴表記錄最長(zhǎng)相同前后綴的長(zhǎng)度信息
字符串的前綴指不包含最后一個(gè)字符的所有以第一個(gè)字符開(kāi)頭的連續(xù)子字符串，后綴指不包含第一個(gè)字符的所有以最后一個(gè)字符結(jié)尾的連續(xù)子字符串
計(jì)算前綴表：a最長(zhǎng)前后綴長(zhǎng)度為0，aa為1，aab為0，aaba為1，aabaa為2，aabaaf為0
上面求得的長(zhǎng)度就是前綴表對(duì)應(yīng)元素，模式串a(chǎn)abaaf前綴表即為010120
當(dāng)文本串和模式串遇到第一個(gè)不匹配字符時(shí)，尋找前一位下標(biāo)在前綴表中對(duì)應(yīng)的元素，該元素是多少就跳到下表為多少的位置繼續(xù)重新匹配
next數(shù)組可以是前綴表也可以是前綴表統(tǒng)一減一后得到的前綴表
匹配過(guò)程時(shí)間復(fù)雜度O(n)，建立前綴表時(shí)間復(fù)雜度O(m)，整個(gè)算法時(shí)間復(fù)雜度O(m+n)比暴力解法O(m*n)效率高很多
力扣344：反轉(zhuǎn)字符串
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：反轉(zhuǎn)字符串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))
????????{
//循環(huán)尋找每次反轉(zhuǎn)的起點(diǎn)
????????????if?(i+k<=s.Length)
????????????{
????????????????Array.Reverse(chars,i,k);
????????????????continue;
//每次有多于k個(gè)字符就反轉(zhuǎn)前k個(gè)
????????????}
????????????Array.Reverse(chars,i,s.Length-i);
//少于k個(gè)就反轉(zhuǎn)這s.Length-1個(gè)字符
????????}
????????string?ss?=?new?string(chars);
????????return?ss;
//char[]型轉(zhuǎn)換成string作為返回值
????}
}
力扣151：反轉(zhuǎn)字符串里的單詞
public?class?Solution?{
?????private?string?RemoveExtraSpaces(string?s)
????{
//使用雙指針?lè)▌h除多余的空格，使句子中只保留單詞與單詞中間的一個(gè)空格
????????int?left?=?0,?right?=?0;
????????StringBuilder?ss?=?new?StringBuilder(s);
//將string轉(zhuǎn)換成StringBuilder方便進(jìn)行操作
????????while?(s.Length>0&&?right<s.Length&&?ss[right]=='?')
????????{
????????????right++;
//找到第一個(gè)字母的位置
????????}
????????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);
//刪除后面的無(wú)效信息，分兩種情況，一種是最后left-1指向空格則刪除left-1后續(xù)所有，一種是left-1指向非空格字符則刪除left之后所有
????????}
????????return?ss.ToString();
//返回值為string類(lèi)型
????}
????public?string?ReverseWords(string?s)
????{
????????char[]?chars=RemoveExtraSpaces(s).ToCharArray();
????????Array.Reverse(chars);
//刪空格，變成字符數(shù)組，反轉(zhuǎn)再挨個(gè)單詞操作
????????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;
//每個(gè)單詞開(kāi)頭一定在空格后面
????????????}
????????????if?(entry&&?chars[i]=='?'&&?chars[i-1]!='?')
????????????{
????????????????end?=?i?-?1;
????????????????entry?=?false;
????????????????Array.Reverse(chars,start,end-start+1);
//單詞結(jié)尾后面有空格，將結(jié)尾標(biāo)記在空格前一位然后反轉(zhuǎn)開(kāi)頭到結(jié)尾所有字符
????????????}
????????????if?(entry&&?i==chars.Length-1)
????????????{
????????????????end?=?i;
????????????????entry?=?false;
????????????????Array.Reverse(chars,start,end-start+1);
//最后一個(gè)單詞結(jié)尾沒(méi)有空格，將結(jié)尾標(biāo)記在最后一個(gè)字母上然后反轉(zhuǎn)開(kāi)頭到結(jié)尾所有字符
????????????}
????????????
????????}
????????string?a?=?new?string(chars);
????????return?a;
????}
}
力扣28：找出字符串中第一個(gè)匹配字符串的下標(biāo)
//使用KMP算法，構(gòu)建next數(shù)組，進(jìn)行匹配節(jié)省時(shí)間
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循環(huán)不用if判斷的原因是前后綴不匹配就要讓i循環(huán)退到匹配的位置或第0位
????????????}
????????????if?(s[i]==s[j])
????????????{
????????????????i++;
????????????}
????????????next[j]?=?i;
//每次循環(huán)給j賦值為當(dāng)前距離第0位的距離即為返回匹配時(shí)的開(kāi)始位置
????????}
????}
????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;
//匹配的上則返回這次匹配的開(kāi)始位置
????????????}
//這里與制作next數(shù)組的原理相同，只是判斷是否匹配的地方換成了兩個(gè)字符串
????????}
????????return?-1;
????}
}
力扣459：重復(fù)的子字符串
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數(shù)組的部分與上一題相同
????????}
????}
????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;
//難點(diǎn)在于這里如何判斷是有循環(huán)的，首先若能夠有循環(huán)最后一位的next數(shù)組對(duì)應(yīng)值一定不是0，其次由于前后綴分別不包含頭尾元素，最長(zhǎng)相等前后綴長(zhǎng)度一定是總長(zhǎng)度減去進(jìn)行循環(huán)的字符串長(zhǎng)度，因此若總長(zhǎng)度 能除開(kāi) 總長(zhǎng)度減去最長(zhǎng)相等前后綴得到的長(zhǎng)度則說(shuō)明有循環(huán)存在，除不開(kāi)有余數(shù)說(shuō)明不存在循環(huán)
????????}
????????return?false;
????}
}
