首页 > 学生作文 > 读后感 > 读后感800字 >

C++ 高级字符串处理 - 图文

由天下分享时间：2024/12/12 21:54:21 加入收藏我要投稿点赞

字符串专题

一、字符串操作

1.定义

char str1[200]; string str2;

2.读入

gets(str1) 遇到回车时终止，C++11标准中被删除 scanf(\ 默认遇到回车或空格时终止 cin>>str1 遇到回车或空格时终止 getline(cin,str2) 遇到回车终止

cin.get(str1,200) 遇到回车终止，可以接收空格 cin.getline(str1,200) 同cin.get()

万能大法：ch=getchar()

3.库函数

1.string 转char数组有两种方法：c_str()和data()，常用的是c_str()，data()方法不会附加文件结束标记'\\0'。示例：

string str; char chs[200];

strcpy(chs,str.c_str());

// chs = str.c_str(); 错误示范

2.char 数组常用的操作： strcpy(chs1,chs2) strcmp(chs1,chs2) strlen(chs) strcat(chs1,chs2); strchr(chs,ch) strstr(chs1,chs2) strrev(chs1)

3.string常用操作： string str(\ string str1(\ string str1(\ string str2(str1,2) string str2(str1,2,2) string str(10,'H'); str.front() str.back() str.at(2) str.substr(2,2) str.size() // length() 同 str.clear() str.append(str2) str.replace(2,2,\ str.find(str1) str.rfind(str1) reverse(str.begin(),str.end())

4.应用

【例1-1】编辑距离(https://www.luogu.com.cn/problem/P2758) 题目描述

设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种： 1、删除一个字符； 2、插入一个字符；

3、将一个字符改为另一个字符；！皆为小写字母！输入格式

第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。输出格式

只有一个正整数，为最少字符操作次数。输入样例 sfdqxbw gfdgw 输出样例 4

【尺取法】POJ3061(http://poj.org/problem?id=3061) 题目描述

给定长度为n的数列a0,a1…an-1以及整数S，求出总和不小于S的连续子序列的长度的最小值。如果不存在输出0。 10

5 1 3 5 10 7 4 9 2 8 15 输出样例 2

【例1-2】Kirinriki (http://acm.hdu.edu.cn/showproblem.php?pid=6103) 题目描述

定义字符串A和B的距离如下：

??????

????????,??=??|?????????????????|

??????

其中两个字符之间的距离定义为其ASCII码的差值。

请在给定的字符串S中找出互不相交的两个字串，使得他们之间的距离不大于m且长度尽可能长。输入格式

第一行输入一个整数，表示测试样例数。

每组测试样例第一行为一个整数m，表示字串之间的最大距离。第二行输入一个字符串S。输出格式

输出字串的最大长度。输入样例 1

abcdefedcb 输出样例 5 数据范围 T<=100

0<=m<=5000

组成字符串的都是小写字母, 2≤|S|≤5000 所有字符串的长度之和不大于20000 样例解释

abcde和fedcb，他们的距离为：

abs('a'-'b')+abs('b'-'c')+abs('c'-'d')+abs('d'-'e')+abs('e'-'f')=5

【练习】

1. Substrings(http://acm.hdu.edu.cn/showproblem.php?pid=1238) 题目大意：给定一些字符串，在其中求满足条件的最长字串X，X或X的翻转是任意字符串的子串。

二、字符串哈希

1.定义

Hash，一般翻译做散列，或音译为哈希，是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

2. 背景

寻找字符串S中的匹配串T出现的位置或者出现的次数问题，一般用到字符串Hash算法。朴素的思想是枚举起始位置，用O(m)的复杂度检查是否匹配，这样总的复杂度就是O(nm)，我们可以不使用以上算法，而直接判断子串的Hash值与匹配串的Hash值是否相等，这个过程叫做字符串Hash。

多数字符串Hash问题都可以用KMP求解，如果需要从主串中每次选取两个子串判断是否匹配的问题，用字符串Hash求解比较方便

3. 算法

在通常情况下，如果字符串中只有小写字母，我们可以用26进制数来作为散列值，复杂度为O(m)。而基于以上背景，该算法比那个不能给求解的方法带来改善，我们需要学习一种O(1)的Hash算法。假设字符串为S=c1c2…cm，定义哈希函数

H(S)=(c1bm-1+c2bm-2+…+cmb0)mod h

其中b和h为互质常数，且b

以上函数可以写作递推形式，如果H(S,k)表示字符串S前k个字符的散列值，那么在不考虑取模的情况下，我们可以得到：

H(S,k+1)=H(S,k)*b+ck+1

假设现在要判断字符串S=c1c2…cm从位置k开始长度为n的子串

S'=ck+1ck+2…ck+n与另一匹配串的哈希值是否相等，则 H(S')=H(S,k+n)-H(S,k)*bn 只要预处理出所有的bx，就可以在O(1)时间内得到任意子串的哈希值，从而完成字符串匹配。

建议：在实际实现时，可以利用32位或64位无符号整型计算哈希值，利用整型的自然溢出实现求模运算。