在CSP里面好多道“水题“基本都离不开字符串/数组的模拟

滚动哈希，字典树，DP几个强强联合基本可以横扫所有难度的字符串算法了，所以在这个task里会好好消化其中前二

字符串和数组有很多相似之处，比如同样使用下标的方式来访问单个字符。根据字符串的特点，将字符串问题分为以下几种：

• 字符串匹配问题
• 子串相关问题
• 前缀 / 后缀相关问题
• 回文串相关问题
• 子序列相关问题

关于字符串的字符编码：

• ASCII（英语为主的语言）

• Unicode（多语言，其中最常用的就是UTF-8编码）。UTF-8：将Unicode字符根据大小编成1-6个字节，英文1个字节，汉字通常是3个字节。

字符串匹配问题（模式匹配,，Pattern Matching) ：

• 单模式串匹配：从文本串中找到特定串的所有出现位置。这次主要训练了KMP算法（基于前缀搜索方法）。

• 多模式串匹配：文本串中找模式串P，其中P是模式串p的集合，找到集合P中p的所有出现位置。

基操

125.验证回文串

测试用例：

a man,a plAn,a canal:Panama

< cctype >

isalnum( )：bool型，判断是否为有效字符（十进制数字/字母

tolower()：char型，将有效字符转为小写字母（toupper

AC:对撞指针--left&right

#include<iostream>
#include<string>
using namespace std;

bool ValidPalindrome(string &s){
    string sgood;
    for(char c:s){
        if(isalnum(c)){
            sgood+=tolower(c);
        }
    }
    int n=sgood.size();
    for(int left=0,right=n-1;left<right;){
        if(sgood[left]!=sgood[right])
            return false;//不是回文串
        ++left;
        --right;
    }
    return true; 
}

int main(){
    string s;
    cin>>s;
    if(ValidPalindrome(s))
        cout<<"true"<<endl;
    else   cout<<"false"<<endl;
    return 0;
}

344.反转字符串

UNAC：翻转字符串角标的关系 i&n-1-i ( ≠ i&n-i )

string ReverseString(string &s){
    int n=s.size();
    for(int i=0;i<=n/2;++i){
        swap(s[i],s[n-i]);//s[n-1-i]
    }
    return s;
}

AC：双指针--left&right

n&n-1-i 无法替代lr指针（for循环判断不会出错

#include<iostream>
#include<string>
using namespace std;
string reverse(string &s){
    int left=0;
    int right=s.size()-1-left;
    for(;left<right;++left,--right){
        swap(s[left],s[right]);
    }
    cout<<s<<endl;
    return s;
}

int main(){
    string s;
    cin>>s;
    reverse(s);
    cout<<"[\"";
    for(int i=0;i<s.size()-1;i++){
        cout<<s[i]<<"\",\"";
    }
    cout<<s[s.size()-1]<<"\"]";
}

557.翻转字符串中的单词III

AC：使用额外空间

#include<iostream>
#include<string>
using namespace std;

string reverse(string &s){
    string word;//开新串存翻转后字符串
    int n=s.size();
    int i=0;
    while(i<n){
        int start=i;//单词的起始下标
        while(i<n&&s[i]!=' '){//始
            i++;
        }
        for(int p=start;p<i;p++){
            word.push_back(s[start+i-1-p]);//翻转后存入
        }
        while(i<n&&s[i]==' '){//终
            i++;
            word.push_back(' ');
        }
        return word;
    }
}

int main(){
    string s,rev;
    cin>>s;
    rev=reverse(s);
    cout<<rev;
    return 0;
}

字符串单模式匹配

BruteForce算法

BF暴力匹配：双层for循环

• 成功：i++; j++;

• 失败：i回溯；j置0；

RabinKarp算法（滚动哈希算法

RK，使用哈希函数在文本中搜索

。。。看官方讲解的时候只能说什么依托答辩，一堆高级名词直接劝退，后来找到一篇CSDN直呼牛蛙

（参考：滚动哈希——干脆叫前缀和得了——CSDN)

KMP算法

（参考：题解：多图预警