4.2 字符串
C++ string 字符串函数详解
#include <string>
长度：size(), length()，二者作用基本相同
访问：1.元素下标从0到size()-1。2. 通过迭代器iterator访问
元素操作：插入insert()、删除erase()、清空clear()
按照字典序进行大小比较：<, >, <=, >=, ==, !=
寻找特等字符或字符串：find()，返回字符串的子串:substr()
4.2 字符串处理
例题4.1 特殊乘法
提交网址
#include <iostream>
#include <string>
using namespace std;
int main(){
string str1, str2;
while(cin >> str1 >> str2){
int sum = 0;
for(int i=0; i<str1.length(); i++){
for(int j=0; j<str2.length(); j++){
sum += (str1[i] - '0') * (str2[j] - '0');
}
}
printf("%d\n", sum);
}
return 0;
}
例题4.2 密码翻译
提交网址
#include <iostream>
#include <string>
using namespace std;
int main(){
string str;
getline(cin, str);
for(int i=0; i<str.length(); i++){
if(str[i] == 'z' || str[i] == 'Z'){
str[i] -= 25;
}else if((str[i] >= 'A' && str[i] <= 'Y') || (str[i] >= 'a' && str[i] <= 'y')){
str[i] ++;
}
}
cout << str << endl;
return 0;
}
例题4.3 简单密码
提交网址
#include <iostream>
#include <string>
using namespace std;
int main(){
string str;
while(getline(cin, str)){
if(str == "ENDOFINPUT") break;
getline(cin, str);
for(int i=0; i<str.length(); i++){
if(str[i] >= 'A' && str[i] <= 'Z'){
str[i] = (str[i] - 'A' - 5 + 26) % 26 + 'A';
}
}
cout << str << endl;
getline(cin, str);
}
return 0;
}
例题4.4 统计字符
提交网址
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int num[128];
string str1, str2;
while(getline(cin, str1)){
if(str1 == "#") break;
getline(cin, str2);
memset(num, 0, sizeof(num));
for(int i=0; i<str2.length(); i++){
num[str2[i]]++;
}
for(int i=0; i<str1.length(); i++){
printf("%c %d\n", str1[i], num[str1[i]]);
}
}
return 0;
}
例题4.5 字母统计
提交网址
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int num[26];
string str;
while(getline(cin, str)){
memset(num, 0, sizeof(num));
for(int i=0; i<str.length(); i++){
if(str[i] >= 'A' && str[i] <= 'Z'){
for(int j=0; j<26; j++){
if(str[i] == j + 'A'){
num[j]++;
}
}
}
}
for(int i=0; i<26; i++){
printf("%c:%d\n", 'A' + i, num[i]);
}
}
return 0;
}
习题4.1 skew数
提交网址
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int main(){
string str;
while(getline(cin, str)){
int len = str.length();
int sum = 0;
for(int i=0; i<len; i++){
sum += (str[i] - '0') * (int)(pow(2, len-i) - 1);
}
printf("%d\n", sum);
}
return 0;
}
习题4.2 单词替换
提交网址
#include <iostream>
#include <cstring>
using namespace std;
int main(){
string str1, str2, str3, s, a, b;
while(getline(cin, str1)){
getline(cin, str2);
getline(cin, str3);
s = " " + str1 + " ";
a = " " + str2 + " ";
b = " " + str3 + " ";
while(true){
int pos = s.find(a);
if(pos == string::npos){
break;
}
s = s.replace(pos, a.length(), b);
}
cout << s.substr(1, s.length()-2) << endl;
}
return 0;
}
习题4.3 首字母大写
提交网址
#include <iostream>
#include <cstring>
using namespace std;
int main(){
string str;
while(getline(cin, str)){
if(str[0] >= 'a' && str[0] <= 'z'){
str[0] -= 32;
}
for(int i=0; i<str.length()-1; i++){
if(str[i] == ' ' || str[i] == '\t' || str[i] == '\r'){
if(str[i+1] >= 'a' && str[i] <= 'z'){
str[i+1] -= 32;
}
}
}
cout << str << endl;
}
return 0;
}
习题4.4 浮点数加法
提交网址
#include <iostream>
#include <cstring>
using namespace std;
int main(){
string x, y;
while(cin >> x >> y){
int pos1 = x.find('.');
int pos2 = y.find('.');
if(pos1 > pos2){
y.insert(0, pos1 - pos2, '0');
}else{
x.insert(0, pos2 - pos1, '0');
}
if(x.length() < y.length()){
x.insert(x.length(), y.length() - x.length(), '0');
}else{
y.insert(y.length(), x.length() - y.length(), '0');
}
int carry = 0;
for(int i=x.length()-1; i>=0; i--){
if(x[i] == '.') continue;
int tmp = (x[i] - '0') + (y[i] - '0') + carry;
if(tmp >= 10){
carry = 1;
x[i] = tmp - 10 + '0';
}else{
carry = 0;
x[i] = tmp + '0';
}
}
if(carry == 1){
x.insert(0, "1");
}
cout << x << endl;
}
return 0;
}
习题4.5 后缀子串排序
提交网址
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
string str;
vector<string> subs;
cin >> str;
int len = str.length();
for(int i=1; i<=len; i++){
subs.push_back(str.substr(len-i, i));
}
sort(subs.begin(), subs.end());
for(auto it = subs.begin(); it != subs.end(); it++){
cout << *it << endl;
}
return 0;
}
4.3 字符串匹配
图解算法：KMP算法
例题4.6 Number Sequence
这个代码是照着书上敲的。如果没有耐心看文章或者懒得自己理解（毕竟假期宅在家脑子也不是很愿意运转），可以看视频先理解！
#include <iostream>
using namespace std;
const int MAXM = 10000;
const int MAXN = 1000000;
int nextTable[MAXM];
int pattern[MAXM];
int text[MAXN];
void GetNextTable(int m){
int j = 0;
nextTable[j] = -1;
int i = nextTable[j];
while(j < m){
if(i == -1 || pattern[j] == pattern[i]){
i++; j++;
nextTable[j] = i;
}else{
i = nextTable[i];
}
}
return;
}
int KMP(int n, int m){
GetNextTable(m);
int i=0, j=0;
while(i < n && j < m){
if(j == -1 || text[i] == pattern[j]){
i++; j++;
}else{
j = nextTable[j];
}
}
if(j == m){
return i - j + 1;
}else{
return -1;
}
}
int main(){
int caseNumber;
scanf("%d", &caseNumber);
while(caseNumber--){
int n, m;
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++){
scanf("%d", &text[i]);
}
for(int i=0; i<m; i++){
scanf("%d", &pattern[i]);
}
printf("%d\n", KMP(n, m));
}
return 0;
}
例题4.7 Oulipo
也是照着书上敲的！（如果是我做这题，估计会选择用string的find来做）
#include <iostream>
#include <string>
using namespace std;
const int MAXM = 10000;
int nextTable[MAXM];
void GetNextTable(string pattern){
int m = pattern.size();
int j = 0;
nextTable[j] = -1;
int i = nextTable[j];
while(j < m){
if(i == -1 || pattern[j] == pattern[i]){
i++; j++;
nextTable[j] = i;
}else{
i = nextTable[i];
}
}
return;
}
int KMP(string text, string pattern){
GetNextTable(pattern);
int number = 0;
int n = text.size(), m = pattern.size();
int i = 0, j = 0;
while(i < n){
if(j == -1 || text[i] == pattern[j]){
i++; j++;
}else{
j = nextTable[j];
}
if(j == m){
number++;
j = nextTable[j];
}
}
return number;
}
int main(){
int caseNumber;
scanf("%d", &caseNumber);
while(caseNumber--){
string pattern, text;
cin >> pattern >> text;
printf("%d\n", KMP(text, pattern));
}
return 0;
}
习题4.6 字符串匹配
提交网址
在这题中，我发现c++竟然还有正则表达式库！好耶！！！（真的太适合这题了，妙啊！
C++正则表达式regex库使用方法总结
（其实就是不想写KMP啦！）
#include <iostream>
#include <string>
#include <regex>
#include <vector>
using namespace std;
int main(){
int n;
while(scanf("%d", &n) != EOF){
vector<string> in;
string match;
string str;
for(int i=0; i<n; i++){
cin >> str;
in.push_back(str);
}
cin >> match;
regex re(match, regex_constants::icase);
for(int i=0; i<n; i++){
if(regex_match(in[i], re)){
cout << i + 1 << " " << in[i] << endl;
}
}
}
return 0;
}
习题4.7 String Matching
和 例题4.7 Oulipo 一模一样。这次不用KMP，用find函数来做一遍。（短小精悍！
#include <iostream>
#include <string>
using namespace std;
int main(){
string text, pattern;
while(cin >> text >> pattern){
int cnt = 0, pos = text.find(pattern);
while(pos != string::npos){
cnt++;
pos = text.find(pattern, pos + 1);
}
printf("%d\n", cnt);
}
return 0;
}
|