02-KMP算法
目的：在一个字符串中找一个字串朴素暴力解法：在主串中挨个找，匹配返回位置，不匹配回到下一个位置问题：例如前面以及匹配过ab的组合，子串中也有ab,那么可以直接比较子串ab后面的字符和主串ab后面的字符,否则在挨个比较就重复了故而提出KMP算法：1.需要得到前缀表 next[]数组eg:设子串T=“aabaaf”，求T的前缀表 即next数组1>第一个子串 t0=“a”，没有前缀也没有后缀 next[0]=02>第二个子串 t1=“aa”，前缀为”a”，后缀也为”a” next[1]=13>第三个子串 t2=“aab”，该子串后缀中一定会有”b”，前缀中一定不含有”b”，没有相等的前后缀 next[2]=04>第四个子串 t3=“aaba”，最大相等前后缀为”a”，长度为1，next[3]=15>第五个子串 t4=“aabaa”，最大相等前后缀为”aa”，长度为2，next[4]=26>第六个子串是t5=“aabaaf”，该子串的后缀中一定会有”f”，前缀中一定不含有”f”，则其没有相等的前后缀 next[5]=0
next[]数组的作用：到主串的j, ...
数组入门
一.c++ —动态数组 std::vector (用using … std; std省略)1.作用：封装了可以改变大小的数组，使其成为存储和管理动态数据集合的首选方式2.用法： vector<元素类型>变量名;3.常用操作：1>初始化vector v; // 创建一个空的 int 类型的 vectorvector v(5, 10); // 创建一个包含 5 个元素的 vector，每个元素初始化为 10vector v = {1, 2, 3, 4, 5}; // 使用列表初始化2>添加元素(插入元素)v.push_back(10); // 在 vector 的末尾添加一个元素v.insert(v.begin(), 20); // 在 vector 的开头插入一个元素3>访问元素int first = v.front(); // 获取 vector 的第一个元素int last = v.back(); // 获取 vector 的最后一个元素int element = v[3]; // 获取索引为 3 的元素4>删除元素v.pop_back(); // ...
11.数字反转（升级版）
题目：text代码：
include using namespace std;
string transfer(string s){ reverse(s.begin(), s.end()); //知识点1 return s;}
string zero(string s){ int pos = s.find(‘0’); while(pos == 0 && s.size() > 1){ s = s.erase(pos, 1); pos = s.find(‘0’); } return s;}
int main(){ string s, temp; cin >> s; int pos = s.find(‘.’);
if (pos != string::npos) { // 小数 //知识点2
temp = s;
s = s.substr(0, pos);
s = transfer(s);
s = zero(s) + temp[pos] ...
12.斯诺登的密码
题目：alt text代码：
include includeusing namespace std;/1.输入，string 先对格式不做要求2.找数字 存入数组中，利用for循环遍历 存储到数组3.平方 取模 去0
/int main(){ string s[6]; string snum[26] = {“one”,”two”,”three”,”four”,”five”,”six”,”seven”,”eight”,”nine”,”ten”,”eleven”,”twelve”,”thirteen”,”fourteen”,”fifteen”,”sixteen”,”seventeen”,”eighteen”,”nineteen”,”twenty”,”a”,”both”,”another”,”first”,”second”,”third”}; int num[26] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,1,2,1,1,2,3}; int data[6] = {0}; int j = 0;
...
5. kotori和素因子（A组，B组）
题目：代码：
include using namespace std;/思路总结：1.保存1000以内的质数—埃拉托斯特尼筛法2.求出所有整数的所有素因子—动态二维数组3.dfs求出最小素因子之和
/int ans = 9999999;int n;int vis[10001];
vectorv[100];const int MAX = 1001;bool prime[MAX];// 埃拉托斯特尼筛法void init(){ fill(prime,prime + MAX,true); //初始化全为质数 for(int i = 2 ; i i < MAX; ++i){ if(prime[i]){ for(int j = i i; j < MAX; j+=i){ prime[j] = false; } } }}void dfs(int d,int sum){//重点 if(d == n){//先写退出条件—深度达到最大值 ans = m ...
10.单词覆盖还原
题目：heo/source/_posts/洛谷-题单-字符串-代码/10.单词覆盖还原.md代码：
include include using namespace std;
int main(){ int numboy = 0,numgirl = 0; string s; cin>>s;
for(int i = 0; i<s.size();i++){
//cout<<"i-->"<<i<<" ";
if(s[i] == 'b'){
if(s[i + 1] == 'o'){
if(s[i + 2] == 'y'){
numboy++;
i = i+2;
// cout<<endl<<"boy"& ...
9.小果的键盘
题目：代码：
include include using namespace std;
int main(){ int n; string s; cin>>n>>s; int num = 0;
for(int i = 0;i < s.size() - 1;i++){
if(s[i] == 'V' && s[i + 1] == 'K'){
num++;
s[i] = s[i + 1] = 0;
}
}
int pos = s.find("VV");
if(pos >= 0){
num++;
}
else{
pos = s.find("KK");
if(pos >= 0) num++;
}
cout<<num;
return 0;
}错误原因：1.s.find(“VV”)函数引 ...
8.手机
题目：代码：
include include using namespace std;
int main(){ string str; int num = 0; getline(cin,str); for(int i = 0; i < str.size(); i++){ if(str[i] == ‘a’ ||str[i] == ‘d’ ||str[i] == ‘g’ ||str[i] == ‘j’ ||str[i] == ‘m’ ||str[i] == ‘p’||str[i] == ‘t’ ||str[i] == ‘w’){ num++; } else if(str[i] == ‘b’ ||str[i] == ‘e’ ||str[i] == ‘h’ ||str[i] == ‘k’ ||str[i] == ‘n’ ||str[i] == ‘q’ ||str[i] == ‘u’ ||str[i] == ‘x’){ num = num + 2; } ...
4.（A组，B组）
题目：代码：
include include using namespace std;
int main(){ long long n,result = 0; string s; cin>>n>>s; int num[26] = {0},dp[26] = {0}; for(int i = 0; i < n;i++){ result = result + dp[s[i] - ‘a’]; dp[s[i] - ‘a’] += i - num[s[i] - ‘a’]; num[s[i] - ‘a’]++; } cout<<result; return 0;}方法思想：动态规划eg:abcbcc判断“abb”式的大体思想是：第一个字符和第二个字符不同，第二个字符和第三个字符相同 == 每遍历一个字符“b”，判断在此之前有多少个“ab”重难点:如何判断在此之前有多少个“ab”：用当前遍历的元素个数 - 该元素此前出现的次数 剩下的就是与该元素不同的元素，只要不同就能构 ...
3.红色和紫色
题目：代码：
include using namespace std;
int main(){ int n = 0; int m = 0; while(n < 1){ cin>>n; } while(m < 1){ cin>>m; } if(n % 2 == 1 && m % 2 == 1){ cout<<”akai”; } else{ cout<<”yukari”; } return 0;}疑问：为什么(n % 2 == 1 && m % 2 == 1)这个是对的，(n * m % 2 == 1 )这个是错的