c标准库函数转换“多字节”和“宽字符”字符串的问题
[问题点数：200分，结帖人NorthCan]
本版专家分：2292
2011年12月 硬件/嵌入开发大版内专家分月排行榜第一2011年8月 硬件/嵌入开发大版内专家分月排行榜第一
2012年1月 硬件/嵌入开发大版内专家分月排行榜第二2011年11月 硬件/嵌入开发大版内专家分月排行榜第二2011年10月 硬件/嵌入开发大版内专家分月排行榜第二2011年9月 硬件/嵌入开发大版内专家分月排行榜第二
2012年3月 硬件/嵌入开发大版内专家分月排行榜第三2012年2月 硬件/嵌入开发大版内专家分月排行榜第三
结帖率 100%
CSDN今日推荐
本版专家分：2292
2011年12月 硬件/嵌入开发大版内专家分月排行榜第一2011年8月 硬件/嵌入开发大版内专家分月排行榜第一
2012年1月 硬件/嵌入开发大版内专家分月排行榜第二2011年11月 硬件/嵌入开发大版内专家分月排行榜第二2011年10月 硬件/嵌入开发大版内专家分月排行榜第二2011年9月 硬件/嵌入开发大版内专家分月排行榜第二
2012年3月 硬件/嵌入开发大版内专家分月排行榜第三2012年2月 硬件/嵌入开发大版内专家分月排行榜第三
本版专家分：3546
本版专家分：67244
2013年8月 Linux/Unix社区大版内专家分月排行榜第一2012年11月 Linux/Unix社区大版内专家分月排行榜第一2012年10月 Linux/Unix社区大版内专家分月排行榜第一2012年9月 Linux/Unix社区大版内专家分月排行榜第一2012年7月 Linux/Unix社区大版内专家分月排行榜第一2012年6月 Linux/Unix社区大版内专家分月排行榜第一2012年5月 Linux/Unix社区大版内专家分月排行榜第一2011年11月 Linux/Unix社区大版内专家分月排行榜第一
2013年6月 Linux/Unix社区大版内专家分月排行榜第二2013年5月 Linux/Unix社区大版内专家分月排行榜第二2013年3月 Linux/Unix社区大版内专家分月排行榜第二2013年1月 Linux/Unix社区大版内专家分月排行榜第二2012年12月 Linux/Unix社区大版内专家分月排行榜第二2012年8月 Linux/Unix社区大版内专家分月排行榜第二2011年12月 Linux/Unix社区大版内专家分月排行榜第二2011年10月 C/C++大版内专家分月排行榜第二2011年10月 Linux/Unix社区大版内专家分月排行榜第二
2012年6月 C/C++大版内专家分月排行榜第三2012年6月 PHP大版内专家分月排行榜第三2012年5月 C/C++大版内专家分月排行榜第三2012年3月 Linux/Unix社区大版内专家分月排行榜第三2012年2月 Linux/Unix社区大版内专家分月排行榜第三2011年11月 C/C++大版内专家分月排行榜第三
本版专家分：2292
2011年12月 硬件/嵌入开发大版内专家分月排行榜第一2011年8月 硬件/嵌入开发大版内专家分月排行榜第一
2012年1月 硬件/嵌入开发大版内专家分月排行榜第二2011年11月 硬件/嵌入开发大版内专家分月排行榜第二2011年10月 硬件/嵌入开发大版内专家分月排行榜第二2011年9月 硬件/嵌入开发大版内专家分月排行榜第二
2012年3月 硬件/嵌入开发大版内专家分月排行榜第三2012年2月 硬件/嵌入开发大版内专家分月排行榜第三
本版专家分：2292
2011年12月 硬件/嵌入开发大版内专家分月排行榜第一2011年8月 硬件/嵌入开发大版内专家分月排行榜第一
2012年1月 硬件/嵌入开发大版内专家分月排行榜第二2011年11月 硬件/嵌入开发大版内专家分月排行榜第二2011年10月 硬件/嵌入开发大版内专家分月排行榜第二2011年9月 硬件/嵌入开发大版内专家分月排行榜第二
2012年3月 硬件/嵌入开发大版内专家分月排行榜第三2012年2月 硬件/嵌入开发大版内专家分月排行榜第三
本版专家分：15964
2012年4月 总版技术专家分月排行榜第二
2012年4月 C/C++大版内专家分月排行榜第一
本版专家分：4612
本版专家分：149
匿名用户不能发表回复！
其他相关推荐字符串编码常用类型：utf-8,gb2312,cp936,gbk等。
python中，我们使用decode()和encode()来进行解码和编码
在python中，使用unicode类型作为编码的基础类型。即
str ---------& unicode ---------&str
u = u'中文' #显示指定unicode类型对象u
str = u.encode('gb2312') #以gb2312编码对unicode对像进行编码str1 = u.encode('gbk') #以gbk编码对unicode对像进行编码str2 = u.encode('utf-8') #以utf-8编码对unicode对像进行编码
u1 = str.decode('gb2312')#以gb2312编码对字符串str进行解码，以获取unicode
u2 = str.decode('utf-8')#如果以utf-8的编码对str进行解码得到的结果，将无法还原原来的unicode类型
如上面代码，str\str1\str2均为字符串类型（str）,给字符串操作带来较大的复杂性。
好消息来了，对，那就是python3，在新版本的python3中，取消了unicode类型，代替它的是使用unicode字符的字符串类型(str),字符串类型（str）成为基础类型如下所示，而编码后的变为了字节类型(bytes)但是两个函数的使用方法不变：
bytes ------& str(unicode)------&bytes
u = '中文' #指定字符串类型对象u
str = u.encode('gb2312') #以gb2312编码对u进行编码，获得bytes类型对象str
u1 = str.decode('gb2312')#以gb2312编码对字符串str进行解码，获得字符串类型对象u1
u2 = str.decode('utf-8')#如果以utf-8的编码对str进行解码得到的结果，将无法还原原来的字符串内容
避免不了的是，文件读取问题：
假如我们读取一个文件，文件保存时，使用的编码格式，决定了我们从文件读取的内容的编码格式，例如，我们从记事本新建一个文本文件test.txt, 编辑内容，保存的时候注意，编码格式是可以选择的，例如我们可以选择gb2312,那么使用python读取文件内容，方式如下：
f = open('test.txt','r')
s = f.read() #读取文件内容,如果是不识别的encoding格式（识别的encoding类型跟使用的系统有关），这里将读取失败
'''假设文件保存时以gb2312编码保存'''
u = s.decode('gb2312') #以文件保存格式对内容进行解码，获得unicode字符串
'''下面我们就可以对内容进行各种编码的转换了'''
str = u.encode('utf-8')#转换为utf-8编码的字符串str
str1 = u.encode('gbk')#转换为gbk编码的字符串str1
str1 = u.encode('utf-16')#转换为utf-16编码的字符串str1
python给我们提供了一个包codecs进行文件的读取，这个包中的open()函数可以指定编码的类型：
import codecs
f = codecs.open('text.text','r+',encoding='utf-8')#必须事先知道文件的编码格式，这里文件编码是使用的utf-8
content = f.read()#如果open时使用的encoding和文件本身的encoding不一致的话，那么这里将将会产生错误
f.write('你想要写入的信息')
知识点：编码格式，下面放一下，文件编码的格式介绍（转来的）：
从文件编码的方式来看，文件可分为ASCII码文件和二进制码文件两种。
ASCII文件也称为文本文件，这种文件在磁盘中存放时每个字符对应一个字节，用于存放对应的ASCII码。例如，数5678的存储形式为：
ASC码： 　11
　　　　　↓ 　　　　↓　　　　↓ 　　　↓
十进制码： 5　　　　　6　　　　7　　　　8 共占用4个字节。ASCII码文件可在屏幕上按字符显示， 例如源程序文件就是ASCII文件，用DOS命令TYPE可显示文件的内容。 由于是按字符显示，因此能读懂文件内容。
二进制文件是按二进制的编码方式来存放文件的。 例如， 数5678的存储形式为： 01110只占二个字节。二进制文件虽然也可在屏幕上显示，但其内容无法读懂。C系统在处理这些文件时，并不区分类型，都看成是字符流，按字节进行 处理。输入输出字符流的开始和结束只由程序控制而不受物理符号(如回车符)的控制。 因此也把这种文件称作“流式文件”。
UCS-2编码(16进制)
UTF-8 字节流(二进制)
0000 - 007F
0080 - 07FF
110xxxxx 10xxxxxx
0800 - FFFF
1110xxxx 10xxxxxx 10xxxxxx
使用Windows记事本的“另存为”，可以在GBK、Unicode、Unicode big endian和UTF-8这几种编码方式间相互转换。同样是txt文件，Windows是怎样识别编码方式的呢？
我很早前就发现Unicode、Unicode big endian和UTF-8编码的txt文件的开头会多出几个字节，分别是FF、FE（Unicode）,FE、FF（Unicode big endian）,EF、BB、BF（UTF-8）。但这些标记是基于什么标准呢？
问题二：最近在网上看到一个ConvertUTF.c，实现了UTF- 32、UTF-16和UTF-8这三种编码方式的相互转换。对于Unicode(UCS2)、 GBK、UTF-8这些编码方式，我原来就了解。但这个程序让我有些糊涂，想不起来UTF-16和UCS2有什么关系。查了查相关资料，总算将这些问题弄清楚了，顺带也了解了一些Unicode的细节。写成一篇文章，送给有过类似疑问的朋友。本文在写作时尽量做到通俗易懂，但要求读者知道什么是字节，什么是十六进制。
0、big endian和little endian
big endian和little endian是CPU处理多字节数的不同方式。例如“汉”字的Unicode编码是6C49。那么写到文件里时，究竟是将6C写在前面，还是将49写在前 面？如果将6C写在前面，就是big endian。还是将49写在前面，就是little endian。
“endian”这个词出自《格列佛游记》。小人国的内战就源于吃鸡蛋时是究竟从大头(Big-Endian)敲开还是从小头(Little-Endian)敲开，由此曾发生过六次叛乱，其中一个皇帝送了命，另一个丢了王位。
我们一般将endian翻译成“字节序”，将big endian和little endian称作“大尾”和“小尾”。
1、字符编码、内码，顺带介绍汉字编码
字符必须编码后才能被计算机处理。计算机使用的缺省编码方式就是计算机的内码。早期的计算机使用7位的ASCII编码，为了处理汉字，程序员设计了用于简体中文的GB2312和用于繁体中文的big5。
GB年)一共收录了7445个字符，包括6763个汉字和682个其它符号。汉字区的内码范围高字节从B0-F7，低字节从A1-FE，占用的码位是72*94=6768。其中有5个空位是D7FA-D7FE。
GB2312 支持的汉字太少。1995年的汉字扩展规范GBK1.0收录了21886个符号，它分为汉字区和图形符号区。汉字区包括21003个字符。2000年的 GB18030是取代GBK1.0的正式国家标准。该标准收录了27484个汉字，同时还收录了藏文、蒙文、维吾尔文等主要的少数民族文字。现在的PC平 台必须支持GB18030，对嵌入式产品暂不作要求。所以手机、MP3一般只支持GB2312。
从ASCII、 GB2312、GBK到GB18030，这些编码方法是向下兼容的，即同一个字符在这些方案中总是有相同的编码，后面的标准支持更多的字符。在这些编码 中，英文和中文可以统一地处理。区分中文编码的方法是高字节的最高位不为0。按照程序员的称呼，GB2312、GBK到GB18030都属于双字节字符集 (DBCS)。
有的中文Windows的缺省内码还是GBK，可以通过GB18030升级包升级到GB18030。不过GB18030相对GBK增加的字符，普通人是很难用到的，通常我们还是用GBK指代中文Windows内码。
这里还有一些细节：
GB2312的原文还是区位码，从区位码到内码，需要在高字节和低字节上分别加上A0。
在DBCS中，GB内码的存储格式始终是big endian，即高位在前。
GB2312 的两个字节的最高位都是1。但符合这个条件的码位只有128*128=16384个。所以GBK和GB18030的低字节最高位都可能不是1。不过这不影 响DBCS字符流的解析：在读取DBCS字符流时，只要遇到高位为1的字节，就可以将下两个字节作为一个双字节编码，而不用管低字节的高位是什么。
2、Unicode、UCS和UTF
前面提到从ASCII、GB2312、GBK到GB18030的编码方法是向下兼容的。而Unicode只与ASCII兼容（更准确地说，是与ISO-8859-1兼容），与GB码不兼容。例如“汉”字的Unicode编码是6C49，而GB码是BABA。
Unicode 也是一种字符编码方法，不过它是由国际组织设计，可以容纳全世界所有语言文字的编码方案。Unicode的学名是"Universal Multiple-Octet Coded Character Set"，简称为UCS。UCS可以看作是"Unicode Character Set"的缩写。
根据维基百科全书(http: //zh.wikipedia.org/wiki/)的记载：历史上存在两个试图独立设计Unicode的组织，即国际标准化组织（ISO）和一个软件制 造商的协会（unicode.org）。ISO开发了ISO 10646项目，Unicode协会开发了Unicode项目。
在1991年前后，双方都认识到世界不需要两个不兼容的字符集。于是它们开始合并双方的工作成果，并为创立一个单一编码表而协同工作。从Unicode2.0开始，Unicode项目采用了与ISO 10646-1相同的字库和字码。
目前两个项目仍都存在，并独立地公布各自的标准。Unicode协会现在的最新版本是2005年的Unicode 4.1.0。ISO的最新标准是3。
UCS规定了怎么用多个字节表示各种文字。怎样传输这些编码，是由UTF(UCS Transformation Format)规范规定的，常见的UTF规范包括UTF-8、UTF-7、UTF-16。
IETF 的RFC2781和RFC3629以RFC的一贯风格，清晰、明快又不失严谨地描述了UTF-16和UTF-8的编码方法。我总是记不得IETF是 Internet Engineering Task Force的缩写。但IETF负责维护的RFC是Internet上一切规范的基础。
3、UCS-2、UCS-4、BMP
UCS有两种格式：UCS-2和UCS-4。顾名思义，UCS-2就是用两个字节编码，UCS-4就是用4个字节（实际上只用了31位，最高位必须为0）编码。下面让我们做一些简单的数学游戏：
UCS-2有2^16=65536个码位，UCS-4有2^31=个码位。
UCS -4根据最高位为0的最高字节分成2^7=128个group。每个group再根据次高字节分为256个plane。每个plane根据第3个字节分为 256行 (rows)，每行包含256个cells。当然同一行的cells只是最后一个字节不同，其余都相同。
group 0的plane 0被称作Basic Multilingual Plane, 即BMP。或者说UCS-4中，高两个字节为0的码位被称作BMP。
将UCS-4的BMP去掉前面的两个零字节就得到了UCS-2。在UCS-2的两个字节前加上两个零字节，就得到了UCS-4的BMP。而目前的UCS-4规范中还没有任何字符被分配在BMP之外。
4、UTF编码
UTF-8就是以8位为单元对UCS进行编码。从UCS-2到UTF-8的编码方式如下：
例如“汉”字的Unicode编码是6C49。6C49在0800-FFFF之间，所以肯定要用3字节模板了：1110xxxx 10xxxxxx 10xxxxxx。将6C49写成二进制是：0110
001， 用这个比特流依次代替模板中的x，得到：11100110 10110001 10001001，即E6
读者可以用记事本测试一下我们的编码是否正确。
UTF -16以16位为单元对UCS进行编码。对于小于0x10000的UCS码，UTF-16编码就等于UCS码对应的16位无符号整数。对于不小于 0x10000的UCS码，定义了一个算法。不过由于实际使用的UCS2，或者UCS4的BMP必然小于0x10000，所以就目前而言，可以认为UTF -16和UCS-2基本相同。但UCS-2只是一个编码方案，UTF-16却要用于实际的传输，所以就不得不考虑字节序的问题。
5、UTF的字节序和BOM
UTF -8以字节为编码单元，没有字节序的问题。UTF-16以两个字节为编码单元，在解释一个UTF-16文本前，首先要弄清楚每个编码单元的字节序。例如收 到一个“奎”的Unicode编码是594E，“乙”的Unicode编码是4E59。如果我们收到UTF-16字节流“594E”，那么这是“奎”还是 “乙”？
Unicode规范中推荐的标记字节顺序的方法是BOM。BOM不是“Bill Of Material”的BOM表，而是Byte Order Mark。BOM是一个有点小聪明的想法：
在UCS 编码中有一个叫做"ZERO WIDTH NO-BREAK SPACE"的字符，它的编码是FEFF。而FFFE在UCS中是不存在的字符，所以不应该出现在实际传输中。UCS规范建议我们在传输字节流前，先传输 字符"ZERO WIDTH NO-BREAK SPACE"。
这样如果接收者收到FEFF，就表明这个字节流是Big-Endian的；如果收到FFFE，就表明这个字节流是Little-Endian的。因此字符"ZERO WIDTH NO-BREAK SPACE"又被称作BOM。
UTF -8不需要BOM来表明字节顺序，但可以用BOM来表明编码方式。字符"ZERO WIDTH NO-BREAK SPACE"的UTF-8编码是EF BB BF（读者可以用我们前面介绍的编码方法验证一下）。所以如果接收者收到以EF BB BF开头的字节流，就知道这是UTF-8编码了。
Windows就是使用BOM来标记文本文件的编码方式的。
6、进一步的参考资料
本文主要参考的资料是 "Short overview of ISO-IEC 10646 and Unicode" (http://www.nada.kth.se/i18n/ucs/unicode-iso10646-oview.html)。
我还找了两篇看上去不错的资料，不过因为我开始的疑问都找到了答案，所以就没有看：
"Understanding Unicode A general introduction to the Unicode Standard" (http://scripts.sil.org/cms/scripts/page.php?site_id=nrsi&item_id=IWS-Chapter04a)"Character set encoding basics Understanding character set encodings and legacy encodings" (http://scripts.sil.org/cms/scripts/page.php?site_id=nrsi&item_id=IWS-Chapter03)
字符串编码与Python 3编码
对编码和字符串编码方式进行总结，同时简单介绍了Python 3中的字符串编码方式...
Python 中的字符串编码
异常处理在之前的学习中我们一直没有接触过。哦对，我们甚至还不知道怎么向程序输入一段字符串。那么我们在这里提供一个小例子。在命令行中，我们输入s = raw_input('Enter something...
字符串编码
print(bytes(&我的&,&utf-8&))
mystr=&hello python&
mystrc=&hello 中国&
print(mystr.encode(&utf-8&))
python——字符串——编码
ASCII&Unicode&UTF-8
ASCII：1字节
Unicode：通常2字节
UTF-8：可变长编码，UTF-8编码把一个Unicode字符编码成1-6字节，常用英文字母编码成1字节，汉字...
python2.7--字符串和编码
我们已经讲过了，字符串也是一种数据类型，但是，字符串比较特殊的是还有一个编码问题。因为计算机只能处理数字，如果要处理文本，就必须先把文本转换为数字才能处理。最早的计算机在设计时采用8个比特...
本节主要说编码相关，以帮助下节了解Python的字符串原理
Python之所以受到程序猿&会写程序的非程序猿的热捧，很大一部分原因是因为其对字符串等数据流的方便快捷处理方式，但是，凡事有利必有弊，python2.x在处理数据过程中，尤其是在处理无比蛋疼博大精深...
python url编码
阅读目录：
二、相关概念
1. 字符与字节
2. 编码与解码
三、Python中的默认编码
1. Python源代码文件的执行过程
2. 默认编码
3. 最佳实践
四、Pyt...
转载自：http://www.jb51.net/article/62155.htm
这篇文章主要介绍了python使用chardet判断字符串编码的方法,涉及Python编码的技巧,具有一定...
没有更多推荐了，个回答mbstring 不是一个默认扩展。这意味着它默认没有被激活。 你必须在 configure 选项中显式激活该模块。 详情参见安装这一节。以下是涉及到 mbstring 的相关配置选项。--enable-mbstring ：激活 mbstring 函数。 要使用 mbstring 函数必须启用这个选项。libmbfl 对 mbstring 是必要的。 libmbfl 被捆绑到了 mbstring。 如果系统已安装 libmbfl，--with-libmbfl[=DIR] 可以指定使用已安装的库。--disable-mbregex ：禁用正则表达式函数中多字节字符的支持。For Linux Mint using PHP 7:sudo apt-get install php7.0-mbstringand don't forget to run:sudo service apache2 restartFedora 9 -- yum install php-mbstring then httpd -k restart to freshen the environment. [EDIT BY danbrown AT php DOT net: This is true for all Red Hat Linux-based distributions using RPM and the `yum` this includes RHEL, Fedora, CentOS, Mandriva, and Intrinsic Linux, among others.]可以去看下PHP相关文档很详细的：题上的应该是粘的PHP文档把
同意去看相关文档，养成好习惯~这个扩展模块记得直接在PHP的ini上配置相关属性就可以了啊Win系统还是linux系统的。如果是win系统，那么很简单，官方已经把mbstring扩展打包在ext文件夹下面了。通常只需要在php.ini添加extension=php_mbstring.dll如果是liunx，如果你没有在当初编译php的时候选择编译mbstring扩展，则你需要动态编译，然后加载到php里面。官方源代码里的ext文件夹下面有mbstring的源代码，cd到那个目录，执行phpize命令，然后分别执行./configure，make，make test，make install。最后在php.ini里面添加extension=mbstring.soyunxunwl.com · 创建者 (已认证)WshenM.com · 站长 (已认证)扫描二维码扫描关注云+社区面试题: 判断字符串是否在另一个字符串中存在？
面试时发现好多人回答不好, 所以就梳理了一下已知的方法, 此文较长, 需要耐心的看下去。从实现和算法原理两方面解此问题， 其中有用PHP原生方法实现也有一些业界大牛创造的算法。
方法一: 语言特性-内置函数
/* strpos示例 */
echo 'match:', strpos('xasfsdfbk', 'xasfsdfbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', strpos('xasfsdfbk', 'fbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', strpos('xasfsdfbk', 'xs') != false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', strpos('xasfsdfbk', 'sfs') !== false ? 'true' : 'false', ';', PHP_EOL;
strpos('xasfsdfbk', 'sfs');
// mb* 相关的函数也可, 比如说mb_strpos是基于字符数执行一个多字节安全的 strpos() 操作。
查找字符串首次出现的位置
PHP 4, PHP 5, PHP 7
查找字符串首次出现的位置（不区分大小写）
PHP 5, PHP 7
计算指定字符串在目标字符串中最后一次出现的位置
PHP 4, PHP 5, PHP 7
计算指定字符串在目标字符串中最后一次出现的位置（不区分大小写）
PHP 5, PHP 7
查找字符串在另一个字符串中首次出现的位置
PHP 4 &= 4.0.6, PHP 5, PHP 7
查找字符串的首次出现
PHP 4, PHP 5, PHP 7
strstr() 函数的忽略大小写版本
PHP 4, PHP 5, PHP 7
计算字串出现的次数
PHP 4, PHP 5, PHP 7
方法二: 语言特性-正则匹配
echo 'match:', str_match('xasfsdfbk', 'xasfsdfbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'fbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'xs') != false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'sfs') !== false ? 'true' : 'false', ';', PHP_EOL;
function str_match($a, $b) {
return preg_match('/' . $b . '/i', $a, $matchs) ? true :
执行匹配正则表达式
PHP 4, PHP 5, PHP 7
执行一个全局正则表达式匹配
PHP 4, PHP 5, PHP 7
方法三: 语言特性-字符串分割
echo 'match:', str_match('xasfsdfbk', 'xasfsdfbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'fbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'xs') != false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'sfs') !== false ? 'true' : 'false', ';', PHP_EOL;
function str_match($a, $b) {
return count(explode($b, $a)) &= 2 ? true :
// strtok 可以么?
// 在分割字符串时，split()与explode()谁快?
标记分割字符串
PHP 4, PHP 5, PHP 7
使用一个字符串分割另一个字符串
PHP 4, PHP 5, PHP 7
用正则表达式将字符串分割到数组中
PHP 4, PHP 5
使用正则表达式分割多字节字符串
PHP 4 &= 4.2.0, PHP 5, PHP 7
通过一个正则表达式分隔字符串
PHP 4, PHP 5, PHP 7
方法四: 很暴力的查找
echo 'match:', str_match('xasfsdfbk', 'xasfsdfbk') !== -1 ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'fbk') !== -1 ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'xs') !== -1 ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'sfs') !== -1 ? 'true' : 'false', ';', PHP_EOL;
function str_match($a, $b) {
if($a == $b) {
$aArr = str_split($a);
$bArr = str_split($b);
$aLen = count($aArr);
$bLen = count($bArr);
if($bLen & $aLen) {
return -1;
$data = [];
$aLastIndex = -1;
$bStartIndex = 0;
for($ai = 0; $ai & $aL $ai++) {
$av = $aArr[$ai];
for($bi = $bStartI $bi & $bL $bi++) {
$bv = $bArr[$bi];
if(($aLastIndex == -1 || $ai == ($aLastIndex + 1)) && $av == $bv) {
if ($aLastIndex != -1 && $ai == ($aLastIndex + 1) && $av != $bv) {
if ($exists) {
$aLastIndex = $
$bStartIndex = $bi + 1;
array_push($data, [
'value' =& $av,
'index' =& $ai
$aLastIndex = -1;
$bStartIndex = 0;
$data = [];
if ($exists && $bLen == $bStartIndex) {
if(!empty($data) && count($data) == $bLen) {
$begin = array_shift($data);
return $begin['index'];
return -1;
方法五: 朴素算法(暴力查找)
echo 'match:', str_match('xasfsdfbk', 'xasfsdfbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'fbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'xs') != false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'sfs') !== false ? 'true' : 'false', ';', PHP_EOL;
function str_match($a, $b) {
$aArr = str_split($a);
$bArr = str_split($b);
$aLen = count($aArr);
$bLen = count($bArr);
for ($ai = 0; $ai &= $aLen - $bL $ai++) {
for ($bi = 0; $bi & $bL $bi++) {
if($aArr[$ai + $bi] != $bArr[$bi]) {
if($bLen == $bi) {
方法六: 字符串查找算法-Rabin-Karp算法
#include &iostream&
#include &string.h&
#define BASE 256
#define MODULUS 101
void RabinKarp(char t[], char p[])
int t_len = strlen(t);
int p_len = strlen(p);
// 哈希滚动之用
int h = 1;
for (int i = 0; i & p_len - 1; i++)
h = (h * BASE) % MODULUS;
int t_hash = 0;
int p_hash = 0;
for (int i = 0; i & p_ i++)
t_hash = (BASE * t_hash + t[i]) % MODULUS;
p_hash = (BASE * p_hash + p[i]) % MODULUS;
int i = 0;
while (i &= t_len - p_len)
// 考虑到哈希碰撞的可能性，还需要用 memcmp 再比对一下
if (t_hash == p_hash && memcmp(p, t + i, p_len) == 0)
cout && p && " is found at index " && i &&
// 哈希滚动
t_hash = (BASE * (t_hash - t[i] * h) + t[i + p_len]) % MODULUS;
// 防止出现负数
if (t_hash & 0)
t_hash = t_hash + MODULUS;
int main()
char t[100] = "It is a test, but not just a test";
char p[10] = "test";
RabinKarp(t, p);
// php 实现
function hash_string($str, $len)
$hash = '';
$hash_table = array(
for ($i = 0; $i & $ $i++) {
$hash .= $hash_table[$str{$i}];
return (int)$
function rabin_karp($text, $pattern)
$n = strlen($text);
$m = strlen($pattern);
$text_hash = hash_string(substr($text, 0, $m), $m);
$pattern_hash = hash_string($pattern, $m);
for ($i = 0; $i & $n-$m+1; $i++) {
if ($text_hash == $pattern_hash) {
return $i;
$text_hash = hash_string(substr($text, $i, $m), $m);
return -1;
echo rabin_karp('hello world', 'ello');
方法七: 字符串查找算法-KMP
public class KMP {
public static int KMPSearch(String txt, String pat, int[] next) {
int M = txt.length();
int N = pat.length();
int i = 0;
int j = 0;
while (i & M && j & N) {
if (j == -1 || txt.charAt(i) == pat.charAt(j)) {
j = next[j];
if (j == N)
return i -
return -1;
public static void getNext(String pat, int[] next) {
int N = pat.length();
next[0] = -1;
int k = -1;
int j = 0;
while (j & N - 1) {
if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
k = next[k];
public static void main(String[] args) {
String txt = "BBC ABCDAB CDABABCDABCDABDE";
String pat = "ABCDABD";
int[] next = new int[pat.length()];
getNext(pat, next);
System.out.println(KMPSearch(txt, pat, next));
方法八: 字符串查找算法-Boyer-Moore
public class BoyerMoore {
public static void getRight(String pat, int[] right) {
for (int i = 0; i & 256; i++){
right[i] = -1;
for (int i = 0; i & pat.length(); i++) {
right[pat.charAt(i)] =
public static int BoyerMooreSearch(String txt, String pat, int[] right) {
int M = txt.length();
int N = pat.length();
for (int i = 0; i &= M - N; i += skip) {
for (int j = N - 1; j &= 0; j--) {
if (pat.charAt(j) != txt.charAt(i + j)) {
skip = j - right[txt.charAt(i + j)];
if (skip & 1){
if (skip == 0)
return -1;
public static void main(String[] args) {
String txt = "BBC ABCDAB AACDABABCDABCDABDE";
String pat = "ABCDABD";
int[] right = new int[256];
getRight(pat,right);
System.out.println(BoyerMooreSearch(txt, pat, right));
方法九: 字符串查找算法-Sunday
public class Sunday {
public static int getIndex(String pat, Character c) {
for (int i = pat.length() - 1; i &= 0; i--) {
if (pat.charAt(i) == c)
return -1;
public static int SundaySearch(String txt, String pat) {
int M = txt.length();
int N = pat.length();
int skip = -1;
for (i = 0; i &= M - N; i += skip) {
for (j = 0; j & N; j++) {
if (txt.charAt(i + j) != pat.charAt(j)){
if (i == M - N)
skip = N - getIndex(pat, txt.charAt(i + N));
if (j == N)
return -1;
public static void main(String[] args) {
String txt = "BBC ABCDAB AACDABABCDABCDABD";
String pat = "ABCDABD";
System.out.println(SundaySearch(txt, pat));
方法十: 字符串查找算法-BF算法(Brute Force)
#include &stdio.h&
#include &stdlib.h&
#include &string.h&
int index_bf(char *s,char *t,int pos);
int index_bf_self(char *s,char *t,int index);
int main()
char s[]="6he3wor"; //标准BF算法中，s[0]和t[0]存放的为字符串长度。
char t[]="3wor";
int m=index_bf(s,t,2); //标准BF算法
printf("index_bf:%d\n",m);
m=index_bf_self(s,t,2); //修改版BF算法，s和t中，不必再存放字符串长度。
printf("index_bf_self:%d\n",m);
字符串S和T中，s[0],t[0]存放必须为字符串长度
例：s[]="7hi baby!"
T[]="4baby"
index_bf(s,t,1);
pos：在S中要从下标pos处开始查找T
(说明：标准BF算法中，为研究方便，s[0],t[0]中存放的为各自字符串长度。)
int index_bf(char *s,char *t,int pos)
if(pos&=1 && pos &=s[0]-'0')
while(i&=s[0]-'0'&&j&=t[0]-'0')
if(s[i]==t[j])
if(j&t[0]-'0')
return i-t[0]+'0';
return -1;
return -1;
修改版，字符串s和t中，不必再包含字符串长度。
例：s[]="hi baby"
t[]="baby"
index_bf_self(s,t,0);
index:在s中，从几号下标开始查找
int index_bf_self(char *s,char *t,int index)
int i=index,j=0;
while(s[i]!='\0')
while(*(t+j)!='\0' && *(s+i+j)!='\0')
if(*(t+j)!=*(s+i+j))
if(*(t+j)=='\0')
return -1;
方法十一: Aho-Corasick 算法
////////////////////////////////////////////////////
程序说明：多模式串匹配的AC自动机算法
自动机算法可以参考《柔性字符串匹配》里的相应章节，讲的很清楚
#include &stdio.h&
#include &string.h&
const int MAXQ = ;
const int MAXN = ;
const int MAXK = 26; //自动机里字符集的大小
struct TrieNode
TrieNode* next[MAXK];
//该节点是否为某模式串的终结点
//以该节点为终结点的模式串个数
TrieNode()
fail = NULL;
memset(next, NULL, sizeof(next));
}*que[MAXQ], *
//文本字符串
char msg[MAXN];
void TrieInsert(char *s)
int i = 0;
TrieNode *ptr =
while(s[i])
int idx = s[i]-'a';
if(ptr-&next[idx] == NULL)
ptr-&next[idx] = new TrieNode();
ptr = ptr-&next[idx];
ptr-&danger =
ptr-&cnt++;
void Init()
char s[100];
root = new TrieNode();
scanf("%d", &N);
for(i = 0; i & N; i++)
scanf("%s", s);
TrieInsert(s);
void Build_AC_Automation()
int rear = 1, front = 0,
root-&fail = NULL;
while(rear != front)
TrieNode *cur = que[front++];
for(i = 0; i & 26; i++)
if(cur-&next[i] != NULL)
if(cur == root)
cur-&next[i]-&fail =
TrieNode *ptr = cur-&
while(ptr != NULL)
if(ptr-&next[i] != NULL)
cur-&next[i]-&fail = ptr-&next[i];
if(ptr-&next[i]-&danger == true)
cur-&next[i]-&danger =
ptr = ptr-&
if(ptr == NULL) cur-&next[i]-&fail =
que[rear++] = cur-&next[i];
int AC_Search()
int i = 0, ans = 0;
TrieNode *ptr =
while(msg[i])
int idx = msg[i]-'a';
while(ptr-&next[idx] == NULL && ptr != root) ptr = ptr-&
ptr = ptr-&next[idx];
if(ptr == NULL) ptr =
TrieNode *tmp =
while(tmp != NULL && tmp-&cnt != -1)
ans += tmp-&
tmp-&cnt = -1;
tmp = tmp-&
int main()
scanf("%d", &T);
while(T--)
Build_AC_Automation();
scanf("%s", msg);
printf("%d\n", AC_Search());
伪方法一: 字符串转数组, 取交集, 判断结果
字符串转数组, 取交集, 判断结果
echo 'match:', str_match('xasfsdfbk', 'xasfsdfbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'fbk') !== false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'xs') != false ? 'true' : 'false', ';', PHP_EOL;
echo 'match:', str_match('xasfsdfbk', 'sfs') !== false ? 'true' : 'false', ';', PHP_EOL;
function str_match($a, $b) {
$aArr = str_split($a);
$bArr = str_split($b);
return join('', array_intersect($aArr, $bArr)) == $b;
// 集合中的元素具有唯一性, 被匹配的字符串中有相同的字符, 将会去重
// 不能保证交集后的元素顺序连续
算法一: Rabin-Karp算法(Karp-Rabin)
Rabin-Karp 算法（也可以叫 Karp-Rabin 算法），由 Richard M. Karp 和 Michael O. Rabin 在 1987 年发表，它也是用来解决多模式串匹配问题的。
它的实现方式有点与众不同，首先是计算两个字符串的哈希值，然后通过比较这两个哈希值的大小来判断是否出现匹配。
选择一个合适的哈希函数很重要。假设文本串为t[0, n)，模式串为p[0, m)，其中 0&m&n，Hash(t[i,j]) 代表字符串t[i, j]的哈希值。
当 Hash(t[0, m-1])!=Hash(p[0,m-1]) 时，我们很自然的会把 Hash(t[1, m]) 拿过来继续比较。在这个过程中，若我们重新计算字符串t[1, m]的哈希值，还需要 O(n) 的时间复杂度，不划算。观察到字符串t[0, m-1]与t[1, m]中有 m-1 个字符是重合的，因此我们可以选用滚动哈希函数，那么重新计算的时间复杂度就降为 O(1)。
Rabin-Karp 算法选用的滚动哈希函数主要是利用
的思想，举个例子，计算字符串t[0, m - 1]的哈希值的公式如下，
Hash(t[0,m-1]) = t[0]*bm-1 + t[1]*bm-2 + ... + t[m-1]*b0
其中的 b 是一个常数，在 Rabin-Karp 算法中，我们一般取值为 256，因为一个字符的最大值不超过 255。上面的公式还有一个问题，哈希值如果过大可能会溢出，因此我们还需要对其取模，这个值应该尽可能大，且是质数，这样可以减小哈希碰撞的概率，在这里我们就取 101。
则计算字符串t[1, m]的哈希值公式如下，
Hash(t[1,m]) = ( Hash(t[0,m-1]) - t[0]*bm-1 ) * b + t[m]*b0
如图, 算法导论上提供的示例图:
算法二: KMP算法(Knuth Morris Pratt)
许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。
这种算法不太容易理解，网上有很多解释，但读起来都很费劲。直到读到Jake Boxer的文章，才真正理解这种算法。下面是对KMP算法解释。
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
因为B与A不匹配，搜索词再往后移。
就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。
接着比较字符串和搜索词的下一个字符，还是相同。
直到字符串有一个字符，与搜索词对应的字符不相同为止。
这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。
一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。
怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。
9.已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：
移动位数 = 已匹配的字符数 - 对应的部分匹配值
因为 6 - 2 等于4，所以将搜索词向后移动4位。
因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。
因为空格与A不匹配，继续后移一位。
逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。
下面介绍《部分匹配表》是如何产生的。
首先，要了解两个概念："前缀"和"后缀"。"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
字符串示例 "bread"
除了最后一个字符以外，一个字符串的全部头部组合
b, br, bre, brea
除了第一个字符以外，一个字符串的全部尾部组合
read, ead, ad, d
部分匹配值实例
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
共有元素长度
[A, AB, ABC]
[BCD, CD, D]
[A, AB, ABC, ABCD]
[BCDA, CDA, DA, A]
[A, AB, ABC, ABCD, ABCDA]
[BCDAB, CDAB, DAB, AB, B]
[A, AB, ABC, ABCD, ABCDA, ABCDAB]
[BCDABD, CDABD, DABD, ABD, BD, D]
"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。
算法三: Boyer-Moore算法
KMP算法并不是效率最高的算法，实际采用并不多。各种文本编辑器的"查找"功能（Ctrl+F），大多采用Boyer-Moore算法。
Boyer-Moore算法不仅效率高，而且构思巧妙，容易理解。1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。
下面是根据Moore教授的例子对Boyer-Moore算法的解释。
假定字符串为"HERE IS A SIMPLE EXAMPLE"，搜索词为"EXAMPLE"。
首先，"字符串"与"搜索词"头部对齐，从尾部开始比较。
这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符（整体上）肯定不是要找的结果。
我们看到，"S"与"E"不匹配。这时，"S"就被称为"坏字符"（bad character），即不匹配的字符。我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。
依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在搜索词"EXAMPLE"之中。所以，将搜索词后移两位，两个"P"对齐。
我们由此总结出"坏字符规则"：
后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。
以"P"为例，它作为"坏字符"，出现在搜索词的第6位（从0开始编号），在搜索词中的上一次出现位置为4，所以后移 6 - 4 = 2位。再以前面第二步的"S"为例，它出现在第6位，上一次出现位置是 -1（即未出现），则整个搜索词后移 6 - (-1) = 7位。
依然从尾部开始比较，"E"与"E"匹配。
比较前面一位，"LE"与"LE"匹配。
比较前面一位，"PLE"与"PLE"匹配。
比较前面一位，"MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"（good suffix），即所有尾部匹配的字符串。注意，"MPLE"、"PLE"、"LE"、"E"都是好后缀。
比较前一位，发现"I"与"A"不匹配。所以，"I"是"坏字符"。
根据"坏字符规则"，此时搜索词应该后移 2 - （-1）= 3 位。问题是，此时有没有更好的移法？
我们知道，此时存在"好后缀"。所以，可以采用"好后缀规则"：
后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置
举例来说，如果字符串"ABCDAB"的后一个"AB"是"好后缀"。那么它的位置是5（从0开始计算，取最后的"B"的值），在"搜索词中的上一次出现位置"是1（第一个"B"的位置），所以后移 5 - 1 = 4位，前一个"AB"移到后一个"AB"的位置。
再举一个例子，如果字符串"ABCDEF"的"EF"是好后缀，则"EF"的位置是5 ，上一次出现的位置是 -1（即未出现），所以后移 5 - (-1) = 6位，即整个字符串移到"F"的后一位。
这个规则有三个注意点：
（1）"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。
（2）如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。
（3）如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，请问这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个"好后缀"只出现一次，则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB"，即虚拟加入最前面的"DA"。
回到上文的这个例子。此时，所有的"好后缀"（MPLE、PLE、LE、E）之中，只有"E"在"EXAMPLE"还出现在头部，所以后移 6 - 0 = 6位。
12.可以看到，"坏字符规则"只能移3位，"好后缀规则"可以移6位。所以，Boyer-Moore算法的基本思想是，每次后移这两个规则之中的较大值。
更巧妙的是，这两个规则的移动位数，只与搜索词有关，与原字符串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。
继续从尾部开始比较，"P"与"E"不匹配，因此"P"是"坏字符"。根据"坏字符规则"，后移 6 - 4 = 2位。
从尾部开始逐位比较，发现全部匹配，于是搜索结束。如果还要继续查找（即找出全部匹配），则根据"好后缀规则"，后移 6 - 0 = 6位，即头部的"E"移到尾部的"E"的位置。
算法四: Sunday算法
Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：1
只不过Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。
如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。下面举个例子说明下Sunday算法。假定现在要在主串”substring searching”中查找模式串”search”。
刚开始时，把模式串与文主串左边对齐：
结果发现在第2个字符处发现不匹配，不匹配时关注主串中参加匹配的最末位字符的下一位字符，即标粗的字符 i，因为模式串search中并不存在i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从 i 之后的那个字符（即字符n）开始下一步的匹配，如下图：
结果第一个字符就不匹配，再看主串中参加匹配的最末位字符的下一位字符，是’r’，它出现在模式串中的倒数第3位，于是把模式串向右移动3位（m - 3 = 6 - 3 = r 到模式串末尾的距离 + 1 = 2 + 1 =3），使两个’r’对齐，如下：
匹配成功。
回顾整个过程，我们只移动了两次模式串就找到了匹配位置，缘于Sunday算法每一步的移动量都比较大，效率很高。
算法五: BF算法(Brute Force)
BF算法核心思想是：首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则T向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。该算法最坏情况下要进行M(N-M+1)次比较，时间复杂度为O(MN)。下面结合图片，解释一下：
S代表源字符串，T代表我们要查找的字符串。BF算法可以表述如下：依次遍历字符串S，看是否字符串S中含有字符串T。
因此，我们依次比较S[0] 和T[0]、S[1] 和T[1]、S[2] 和T[2]……S[n]和T[n] ，从图中我们可知，S[0]-S[7]和T[0]-T[7]依次相等。当匹配到S[8]和T[8]时，两个字符不等。根据定义，此时S和T都要回溯，T向右移动一个字符的位置，即S回溯到S[1]的位置，T回溯到T[0]的位置，再重新开始比较。此时，S[1]和T[0]、S[2]和T[1]……如果再次发现不匹配字符，则再次回溯，即S回溯到S[2]的位置，T回到T[0]的位置。循环往复，直到到达S或者T字符串的结尾。如果是到达S串的结尾，则表示匹配失败，如果是到达T串的结尾，则表示匹配成功。
BF算法优点：思想简单，直接，无需对字符串S和T进行预处理。缺点：每次字符不匹配时，都要回溯到开始位置，时间开销大。
算法六: Aho-Corasick算法
Aho-Corasick算法又叫AC自动机算法，是一种多模式匹配算法。Aho-Corasick算法可以在目标串查找多个模式串，出现次数以及出现的位置。
Aho-Corasick算法主要是应用有限自动机的状态转移来模拟字符的比较，下面对有限状态机做几点说明上图是由多模式串{he,she,his,hers}构成的一个有限状态机：
1.该状态当字符匹配是按实线标注的状态进行转换，当所有实线路径都不满足（即下一个字符都不匹配时）按虚线状态进行转换。
2.对ushers匹配过程如下图所示：
当转移到红色结点时表示已经匹配并且获得模式串
Aho-Corasick算法步骤
Aho-Corasick算法和前面的算法一样都要对模式串进行预处理，预处理主要包括字典树Tire的构造，构建状态转移表（goto），失效函数（failure function），输出表（Output）。
Aho-Corasick算法包括以下3个步骤
构建字典树Tire
构建状态转移表，失效函数（failure function），输出表（Output）
搜索路径（进行匹配）
下面3个步骤分别进行介绍
构建字典树Tire
Tire是哈希树的变种，Tire树的边是模式串的字符，结点就是Tire的状态表，下图是多模式串{he,she,his,hers}的Tire树结构：
构建goto函数、failure function和Output函数
goto函数（状态转移函数）：goto(pre,v)=next,完成这样的任务：在当前状态pre，输入字符v，得到下一个状态next，如果没有下个状态则next=failure。
failure function：失效函数是处理当前状态是failure时的处理。
output函数：当完成匹配是根据状态输出匹配的模式串。
下面是多模式串{he,she,his,hers}的goto函数，failure函数，output函数
failure函数
output函数
多模式串{he,she,his,hers}最终的有限状态机图
一般而言，好的字符串匹配算法要有以下特点:
这是评价一个字符匹配算法最重要的标准。通常要求字符匹配能以线性速度执行。
有几种时间复杂性的评价指标
预处理时间的复杂性
有些算法在进行字符串匹配前需要对模式特征进行预处理
匹配阶段的时间复杂性
字符串匹配过程中执行查找操作的时间复杂性，它通常和文本长度及模式长度相关
最坏情况下的时间复杂性
对一个text进行字符模式匹配时，设法降低各算法的最坏情况下的时间复杂性是目前的研究热点之一
最好情况下的时间复杂性
对一个text进行字符模式匹配时的最好的可能性。
内存占用少
执行预处理和模式匹配不仅需要CPU资源还需要内存资源，尽管目前内存的容量较以前大得多，但为了提高速度，人们常利用特殊硬件。通常，特殊硬件中内存访问速度很快但容量偏小，这时，占用资源少的算法将更具优势。
0 收藏&&|&&0
分享到微博？
我要该，理由是：
在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。