A - 雷同检测
从头开始遍历，遇到相同的字符就输出下标，遍历到相对较短的字符串。
空间复杂度O(1),时间复杂度O(n)
代码:
#include <bits/stdc++.h>
using namespace std;
int main(){
string str1;
string str2;
getline(cin,str1);
getline(cin,str2);
for(int i=0;i<min(str1.size(),str2.size());i++){
if(str1[i]==str2[i]){
cout<<i+1<<" ";
}
}
return 0;
}B - 首字母大写
遍历字符串，判断第一个字母和前一个是空格的字母是否是小写，如果是小写就转换为大写
空间复杂度O(1),时间复杂度O(n)
代码:
#include <bits/stdc++.h>
using namespace std;
int main(){
string str;
getline(cin,str);
for(int i=0;i<str.size();i++){
if(i==0&&str[i]>='a'){
str[i]-=32;
}
if(i>0&&str[i-1]==' '&&str[i]>='a'){
str[i]-=32;
}
}
cout<<str;
return 0;
}C - 大小写转换
遍历字符串，遇到小写字母就转换为大写字母
空间复杂度O(1),时间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
int main(){
string str;
while(cin>>str){
for(int i=0;i<str.size();i++){
if(str[i]>='a'&&str[i]<='z'){
str[i]-=32;
}
}
cout<<str<<endl;
}
return 0;
}D - 数字反转
先判断是正数还是负数，然后利用reverse函数和stoi函数，把字符串反转并把字符串转换为int类型
空间复杂度O(1),时间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
int main(){
string num;
cin>>num;
int a;
if(num[0]=='-'){
reverse(num.begin()+1,num.end());
a=stoi(num);
}
else{
reverse(num.begin(),num.end());
a=stoi(num);
}
cout<<a;
return 0;
} E - 删除单词后缀
利用find函数进行查找，再利用substr函数进行截取
空间复杂度O(1),时间复杂度O(n2)
#include <iostream>
#include <string>
using namespace std;
string s;
int main(){
cin >> s;
if (s.find("er", s.size()-2) != -1)
s = s.substr(0, s.size()-2);
else if (s.find("ly", s.size()-2) != -1)
s = s.substr(0, s.size()-2);
else if (s.find("ing", s.size()-3) != -1)
s = s.substr(0, s.size()-3);
cout << s << endl;
return 0;
}F - 判断字符串是否为回文
利用reverse函数进行反转，然后判断反转后和反转前是否一样
空间复杂度O(1),时间复杂O(n)
#include <bits/stdc++.h>
using namespace std;
int main(){
string str;
cin>>str;
string temp=str;
reverse(str.begin(),str.end());
if(temp==str){
cout<<"yes";
}
else{
cout<<"no";
}
return 0;
} G - 基础数据结构——栈（1）
遍历字符串，遇到 {，(, [ 就入栈，遇到了 }, ), ] 就出栈
空间复杂度O(n),时间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
int main(){
string str;
while(getline(cin,str)){
stack<char> s;
for(int i=0;i<str.size();i++){
if(str[i]=='('||str[i]=='['||str[i]=='{')
s.push(str[i]);
else if(str[i]==')'||str[i]==']'||str[i]=='}'){
if(s.empty())
{
s.push(str[i]);
break;
}
if(str[i]==')'&&s.top()=='(') s.pop();
else if(str[i]==']'&&s.top()=='[') s.pop();
else if(str[i]=='}'&&s.top()=='{') s.pop();
}
}
if(s.size()) cout<<"no"<<endl;
else cout<<"yes"<<endl;
}
return 0;
}H - 字典序
直接进行比较，C++内部重载了string的比较的函数
空间复杂度O(1),时间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
int main(){
string str1,str2;
getline(cin,str1);
getline(cin,str2);
if(str1<str2){
cout<<"YES";
}
else cout<<"NO";
return 0;
}I - 验证子串
利用find函数进行查找
空间复杂度O(1),时间复杂度O(n2)
#include <bits/stdc++.h>
using namespace std;
int main(){
string str1;
string str2;
cin>>str1>>str2;
if(str2.find(str1)!=string::npos) cout<<str1<<" is substring of "<<str2<<endl;
else if(str1.find(str2)!=string::npos) cout<<str2<<" is substring of "<<str1<<endl;
else cout<<"No substring"<<endl;
return 0;
}J - 子串查找
kmp算法，注意可重叠
空间复杂度O(n),时间复杂度O(n+m)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 1000005
using namespace std;
char text[maxn], patten[maxn];
int net[maxn];
int main() {
scanf("%s%s",text,patten);
int la = strlen(text);
int lb = strlen(patten);
memset(net, 0, sizeof(net));
for (int i = 1; i < lb; ++i) {
int j = i;
while (j > 0) {
j = net[j];
if (patten[j] == patten[i]) {
net[i + 1] = j + 1;
break;
}
}
}
int cnt = 0;
for (int i = 0, j = 0; i < la; ++i) {
if (j < lb&&patten[j] == text[i]) {
j++;
}
else {
while (j > 0) {
j = net[j];
if (text[i] == patten[j]) {
j++;
break;
}
}
}
if (j == lb) cnt++;
}
printf("%d\n", cnt);
return 0;
}K - 剪花布条
kmp，不重叠
空间复杂度O(n),时间复杂度O(n+m)
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int c[N];
void getc(string b){
int j=0;
c[j]=0;
for(int i=1;i<b.length();i++){
while(b[i]!=b[j]&&j>0){
j=c[j-1];
}
if(b[i]==b[j]){
j+=1;
}
c[i]=j;
}
}
int KMP(string a,string b){
int cnt=0;
int j=0;
memset(c,0,sizeof(c));
getc(b);
for(int i=0;i<a.length();i++){
if(a[i]!=b[j]&&j>0){
j=c[j-1];
}
if(a[i]==b[j]){
j+=1;
}
if(j==b.length()){
j=0;
cnt++;
}
}
return cnt;
}
int main(){
string a,b;
while(cin>>a)
{
if(a=="#") break;
cin>>b;
cout<<KMP(a,b)<<endl;
}
return 0;
}L - 最长回文子串
利用动态规划进行查找
空间复杂度O(n),时间复杂度O(n2)
#include <bits/stdc++.h>
using namespace std;
int main(){
string str;
cin>>str;
if (str.size()<2) {
return str.size();
}
else{
bool dp[str.size()][str.size()];
int maxlen=1;
int k=0;
for(int i=0;i<str.size();i++){
dp[i][i]=true;
}
for (int j = 1; j < str.size(); j++) {
for (int i = 0; i < j; i++) {
if (str[i] != str[j]) {
dp[i][j] = false;
}
else {
if (j - i < 3) {
dp[i][j] = true;
}
else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > maxlen) {
maxlen = j - i + 1;
k = i;
}
}
}
cout<<maxlen;
}
return 0;
}