首页 / 算法 / 《算法》笔记 15 - 子字符串查找

《算法》笔记 15 - 子字符串查找

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法》笔记 15 - 子字符串查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含12507字，纯文字阅读大概需要18分钟。

内容图文

暴力子字符串查找算法
- 隐式回退
- 性能
- 显式回退
Knuth-Morris-Pratt算法
- 确定有限状态自动机
- DFA的构造
- 性能
Boyer-Moore算法
- 跳跃表的构建
- 性能
Rabin-Karp指纹字符串算法
- 关键思想
- Horner方法
- 性能

字符串的一种基本操作就是子字符串查找。比如在文本编辑器或是浏览器中查找某个单词时，就是在查找子字符串。子字符串的长度（可能为100或1000）相对于整个文本的长度（可能为100万甚至是10亿）来说一般是很短的，在如此多的字符中找到匹配的模式是一个很大的挑战，为此计算机科学家们发明了多种有趣、经典且高效的算法。

暴力子字符串查找算法

要解决这个问题，首先想到的是暴力查找的方法，在文本中模式可能出现匹配的任何地方检查是否匹配。

隐式回退

首先是隐式回退的实现方式，之所以叫隐式回退，在与显式回退的实现对比后就明白原因了。

public static int search(String pat, String txt) {
    int patL = pat.length();
    int txtL = txt.length();

    for (int i = 0; i <= txtL - patL; i++) {
        int j;
        for (j = 0; j < patL; j++)
            if (txt.charAt(i + j) != pat.charAt(j))
                break;
        if (j == patL)
            return i;
    }
    return txtL;
}

用一个索引i跟踪文本，另一个索引j跟踪模式。对于每个i，代码首先将j重置为0，并不断把它加1，直到找到了一个不匹配的字符，或者j增加到patL，此时就找到了匹配的子字符串。

性能

在一般情况下，索引j增长的机会很少，绝大多数时候在比较第一个字符是就会产生不匹配。
在长度为N的文本中，查找长度为M的子字符串时：

在最好情况下，对于每个i，在索引j=0时就发现了不匹配，一共需要进行N次字符比较；
在最坏的情况下，对于前N-1个i，索引j都需要增加到M-1次，才会发现不匹配，最后一次匹配，比如文本和模式都是一连串的A接一个B。这种情况下，对于N-M+1个可能的匹配位置，都需要M次比较，一共需要进行M*(N-M+1)次比较，因为N远大于M，所以忽略小数值后结果为~NM。

显式回退

public static int search1(String pat, String txt) {
    int j, patL = pat.length();
    int i, txtL = txt.length();

    for (i = 0, j = 0; i <= txtL && j < patL; i++) {
        if (txt.charAt(i) == pat.charAt(j))
            j++;
        else {
            i -= j;
            j = 0;
        }
    }
    if (j == patL)
        return i - patL;
    else
        return txtL;
}

与隐式回退一样，也使用了索引i和j分别跟踪文本和模式的字符，但这里的i指向的是匹配过的字符序列的末端，所以这里的i相当与隐式回退中的i+j，如果字符不匹配，就需要回退i和j的位置，将j回退为0，指向模式的开头，将i指向本次匹配的开始位置的下一个字符。
隐式回退的实现方式中，匹配位置的的末端字符是通过i+j指定的，所以只需要将j重新设为0，就实现了文本和模式字符的回退。

Knuth-Morris-Pratt算法

暴力算法在每次出现不匹配时，都会回退到本次匹配开始位置的下一个字符，但其实在不匹配时，就能知道一部分文本的内容，因此可以利用这些信息减少回退的幅度，Knuth-Morris-Pratt算法（简称KMP算法）就是基于这种思想。
比如，假设文本只有A和B构成，那么在查找模式字符串为B A A A A A A A时，如果在匹配到第6个字符时出现不匹配，此时可以确定文本中的前6个字符就是B A A A A B，接下来不需要回退i，只需将i+1, j+2后，继续和模式的第二个字符匹配即可，因为模式的第一个字符是B，而上一次匹配失败的末尾字符也是B。
而对于文本A A B A A B A和模式A A B A A A，在文本的第6个字符处发现不匹配后，应该从第4个字符开始重新匹配，这样就不会错过已经匹配的部分了。
KMP算法的主要思想就是提前判断如何重新开始查找，而这种判断只取决于模式本身。

确定有限状态自动机

KMP算法中不会回退文本索引i，而是使用一个二维数组dfa来记录匹配失败时模式索引j应该回退多远。对于每个字符c，在比较了c和pat.charAt(j)之后，dfa[c][i]表示的是应该和下个文本字符比较的模式字符的位置。
这个过程实际上是对确定有限状态自动机（DFA）的模拟，dfa数组定义的正是一个确定有限状态自动机。DFA由状态（数字标记的圆圈）和转换（带标签的箭头）组成，模式中的每个字符都对应着一个状态，用模式字符串的索引值表示。
【DFA】图和数组
在标记为j的状态中检查文本中的第i个字符时，自动机会沿着转换dfa[txt.charAt(i)][j]前进并继续将i+1，对于一个匹配的转换，就向右移动一位，对于一个不匹配的智慧，就根据自动机的指示回退j。自动机从状态0开始，如果到达了最终的停止状态M，则查找成功。

DFA的构造

DFA是KMP算法的核心，构造给定模式对应的DFA也是这个算法的关键问题。DFA指示了应该如何处理下一个字符。如果在pat.charAt(j)处匹配成功，DFA应该前进到状态j+1。但如果匹配失败，DFA会从已经构造过的模式中获取到需要的信息，以模式 A B A B A C的构造过程举例：
下面表格表示dfa[][]，横向表头表示模式字符，括号中是当前的状态。

1.初始状态，各位置都是0：
-|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)
-:|:-:|:-:|:-:|:-:|:-:|:-:
A|0|0|0|0|0|0|
B|0|0|0|0|0|0|
C|0|0|0|0|0|0|
2.先看字符匹配成功时的情况，这时对应的状态会指向下一个状态：
-|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)
-:|:-:|:-:|:-:|:-:|:-:|:-:
A|1|0|3|0|5|0|
B|0|2|0|4|0|0|
C|0|0|0|0|0|6|

3.在状态0，匹配失败时，无论是B还是C都退到初始状态，重新开始；
4.在状态1，匹配失败时，如果此时的字符为A，则文本为A A，可以跳过状态0，直接到状态1，与A(0)行为一致，所以将A(0)的值复制到B(1)，在DFA中对应的值也为1；而对于字符C，文本为A C，只能退回到状态0,重新开始
-|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)
-:|:-:|:-:|:-:|:-:|:-:|:-:
A|1|1|||||
B|0|2|||||
C|0|0|||||

5.在状态2，匹配失败时，如果此时的字符为B，则文本为A B B，回到状态0；如果是字符C，文本为A B C，也只能退回到状态0。
-|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)
-:|:-:|:-:|:-:|:-:|:-:|:-:
A|1|1|3||||
B|0|2|0||||
C|0|0|0||||

6.在状态3，匹配失败时，如果此时的字符为A，则文本为A B A A，直接到状态1；如果是字符C，文本为A B A C，回到状态0
-|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)
-:|:-:|:-:|:-:|:-:|:-:|:-:
A|1|1|3|1|||
B|0|2|0|4|||
C|0|0|0|0|||

7.在状态4，匹配失败时，如果此时的字符为B，则文本为A B A B B，回到状态0；如果是字符C，文本为A B A B C，回到状态0
-|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)
-:|:-:|:-:|:-:|:-:|:-:|:-:
A|1|1|3|1|5||
B|0|2|0|4|0||
C|0|0|0|0|0||

8.在状态5，匹配失败时，如果此时的字符为a，则文本为A B A B A A，回到状态1；如果是字符B，文本为A B A B A B，回到状态4，因为前面的A B A B都是匹配的，可以跳过。
-|A(0)|B(1)|A(2)|B(3)|A(4)|C(5)
-:|:-:|:-:|:-:|:-:|:-:|:-:
A|1|1|3|1|5|1|
B|0|2|0|4|0|4|
C|0|0|0|0|0|6|

通过以上过程可知，在计算状态为j的DFA时，总能从尚不完整、已经计算完成的j-1个状态中得到所需的信息。

dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
    for (int c = 0; c < R; c++)
        dfa[c][j] = dfa[c][X];
    dfa[pat.charAt(j)][j] = j + 1;
    X = dfa[pat.charAt(j)][X];
}

代码中，用X维护了每次重启时的状态，然后具体的做法是：

匹配失败时，将dfa[][X]复制到dfa[][j]；
匹配成功时，将dfa[pat.chatAt(j)][j]的值设为j+1；
将X更新为dfa[pat.charAt(j)][X]

初始化完成dfa后，查找的代码为：

public int search(String txt) {
    int i, j, N = txt.length(), M = pat.length();
    for (i = 0, j = 0; i < N && j < M; i++) {
        j = dfa[txt.charAt(i)][j];
    }
    if (j == M)
        return i - M;
    else
        return N;
}

性能

在长度为N的文本中，查找长度为M的子字符串时，KMP算法会先初始化dfa，访问模式字符串中的每个字符一次，查找时在最坏情况下，会把文本中的字符都访问一次，所以KMP算法访问的字符最多为N+M个。
KMP算法为最坏情况提供线性级别运行时间的保证。虽然在实际应用中，KMP算法相比暴力算法的速度优势并不明显，因为现实情况下的文本和模式一般不会有很高的重复性。
但KMP算法还有一个非常重要的优点，就是它不需要在输入中回退，这使得KMP算法非常适合在长度不确定的输入流中进行查找，而那些需要回退的算法在处理这种输入时却需要复杂的缓冲机制。

Boyer-Moore算法

KMP算法不需要在输入中回退，但接下来学习的Boyer-Moore算法却利用回退获得了巨大的性能收益。
Boyer-Moore算法是从右向左扫描模式字符串的，比如在查找模式字符串B A A B B A A时，如果匹配了第7、第6个字符，然后在第5个字符处匹配失败，那么就可以知道文本中对应的第5 6 7个字符分别是X A A，而X必然不是B，接下来就可以直接跳到第14个字符了。但并不是每次都能前进这么大的幅度，因为模式的结尾部分也可能出现在文本的其他位置，所以和KMP算法一样，这个算法也需要一个记录重启位置的数组。

跳跃表的构建

有了记录重启位置的数组，就可以在匹配失败时，知道应该向右跳跃多远了，使用一个right数组记录字母表中的每个字符在模式中出现的最靠右的地方，如果字符在模式中不存在，则表示为-1。right数组又称为跳跃表。
构建跳跃表时，先将所有元素设为-1，然后对于0到M-1的j，将right[pat.chatAt(j)]设为j。

public BoyerMoore(String pat) {
    this.pat = pat;
    int M = pat.length();
    int R = 256;
    right = new int[R];
    for (int c = 0; c < R; c++)
        right[c] = -1;
    for (int j = 0; j < M; j++)
        right[pat.charAt(j)] = j;
}

模式 N E E D L E对应的跳跃表为

A   B   C   D   E   ... L   M   N
-1  -1  -1  3   5   -1  4   -1  0

算法会使用一个索引i在文本从左向右移动，用索引j在模式中从右向左移动，然后不断检查txt.charAt(i+j)和pat.charAt(j)是否匹配，如果对于模式中的所有字符都匹配，则查找成功；如果匹配失败，分三种情况处理：

如果造成匹配失败的字符不在模式中，则将模式字符串向右移动j+1个位置，小于这个偏移量都会使模式字符串覆盖的区域中再次包含该字符；

.   .   .   T   L   E   .   .   .
N   E   E   D   L   E
^           ^
i           j

.   .   .   T   L   E   .   .   .
                N   E   E   D   L   E
                ^                   ^
              i增大j+1               j重置为M-1

如果字符在模式中，则根据跳跃表，使该字符和它在模式字符串中对应最右的位置对齐，小于这个偏移量也会使该字符与模式中其它字符重叠；

.   .   .   N   L   E   .   .   .
N   E   E   D   L   E
^           ^
i           j

.   .   .   N   L   E   .   .   .
            N   E   E   D   L   E
            ^
        i增大j-right['N']

如果根据跳跃表得出的结果，无法使模式字符串向右移动，则将i+1，保证至少向右移动了一个位置。

.   .   .   .   .   E   L   E   .   .   .
        N   E   E   D   L   E
        ^           ^
        i           j

.   .   .   .   .   E   L   E   .   .   .
N   E   E   D   L   E
这种情况会使模式字符串向右移动，只能将i+1

.   .   .   .   .   E   L   E   .   .   .
            N   E   E   D   L   E
            ^
            i=i+1

查找算法的实现为：

public int search(String txt) {
    int N = txt.length();
    int M = pat.length();
    int skip;
    for (int i = 0; i <= N - M; i += skip) {
        skip = 0;
        for (int j = M - 1; j >= 0; j--) {
            if (pat.charAt(j) != txt.charAt(i + j)) {
                skip = j - right[txt.charAt(i + j)];
                if (skip < 1)
                    skip = 1;
                break;
            }
        }
        if(skip==0) return i;
    }
    return N;
}

性能

最好情况下，每次跳跃的距离都是M，那么最终只需要N/M次比较。
在最坏的情况下，跳跃失效，等同于暴力算法，比如在一连串A A A A A ...中查找B A A ...，这时需要M*N次比较。
在实际应用场景中，模式字符串中仅含有字符集中的少量字符是很常见的，因此几乎所有的比较都会使算法跳过M个字符，所以一般来说算法需要~N/M次比较。

Rabin-Karp指纹字符串算法

M.O.Rabin和R.A.Karp发明的基于散列的字符串查找算法，与前面两种算法的思路完全不同。计算模式字符串的散列值，然后使用相同的散列函数，计算文本逐位计算M个字符的散列值，如果得出的散列值与模式字符串的散列值相同，就再继续逐字符验证一次，确保匹配成功。
但如果直接按照这种方式，得出的算法效率减比暴力算法还要低很多，而Rabin和Karp发明了一种能够在常数时间内算出M个字符的子字符串散列值的方法，这使得这种算法的运行时间降低到了线性级别。

关键思想

散列函数一般使用除留余数法，除数选择一个尽量大的素数。算法的关键在于只要知道上一个位置M个字符的散列值，就能够快速得算出下一个位置M个字符的散列值。以数字字符串来举例：

2   6   5   3   5 %997=613

5   9   2   6   5   3   5
5   9   2   6   5 %997=442
    9   2   6   5   3 %997=929  
        2   6   5   3   5 %997=613(匹配)

在上面的过程中，模式字符串26535可以看作一个十进制的数字，它要匹配的每M个字符也都可以看作是一个M为的整数，59265用997取余后的结果为442，接下来92653取余时不需要重头计算

59265=5*10000+9265
92653=9265+3*1
所以
92653=(59265-5*10000)*10+3*1

而对于普通的字符串，如果它的字符集中有R个字符，则可以把这些字符串看作是R进制的数字，用t_i表示txt.charAt(i)，则：
x_i=t_iR^M-1+t_i+1R^M-2+...+t_i+M-1R⁰
与得出92653的过程一样，将模式字符串右移一位即等价于将x_i替换为：
x_i+1=(x_i-t_iR^M-1)R+t_i+M

Horner方法

计算散列值时，如果是int值，可以直接取余，但对于一个相当于R进制的数字的字符串，要得出它的余数，就需要用Horner方法，Horner方法的理论依据是，如果在每次算术操作之后都将结果除Q取余，这等价于在完成了所有算术操作之后再将最后的结果除Q取余：

private long hash(String key, int M) {
    long h = 0;
    for (int j = 0; j < M; j++)
        h = (R * h + key.charAt(j)) % Q;
    return h;
}

对于一个R进制的数字，从左至右，将它的每一位数字的散列值乘以R，加上这个数字，并计算除Q的余数。

那么随着索引i的增加，逐位计算M个字符的散列值时，就可以利用跟Horner方法相同的原理了：

public class RabinKarp {
    private String pat;
    private long patHash;
    private int M;
    private long Q;
    private int R = 256;
    private long RM;

    public RabinKarp(String pat) {
        this.pat = pat;
        M = pat.length();
        Q = longRandomPrime();
        RM = 1;
        for (int i = 1; i <= M - 1; i++)
            RM = (R * RM) % Q;
        patHash = hash(pat, M);
    }

    private boolean check(String txt, int i) {
        for (int j = 0; j < M; j++)
            if (pat.charAt(j) != txt.charAt(i + j))
                return false;
        return true;
    }

    private long hash(String key, int M) {
        long h = 0;
        for (int j = 0; j < M; j++)
            h = (R * h + key.charAt(j)) % Q;
        return h;
    }

    // a random 31-bit prime
    private static long longRandomPrime() {
        BigInteger prime = BigInteger.probablePrime(31, new Random());
        return prime.longValue();
    }

    public int search(String txt) {
        int N = txt.length();
        long txtHash = hash(txt, M);
        if (patHash == txtHash && check(txt, 0))
            return 0;
        for (int i = M; i < N; i++) {
            txtHash = (txtHash + Q - RM * txt.charAt(i - M) % Q) % Q;
            txtHash = (txtHash * R + txt.charAt(i)) % Q;
            if (patHash == txtHash)
                if (check(txt, i - M + 1))
                    return i - M + 1;
        }
        return N;
    }
}

性能

取余所选的Q值是一个很大的素数，这里使用的是使用BigInteger.probablePrime生成的一个31位素数，其大小与2³¹接近，那么在将模式字符串的散列值与文本中M个字符的散列值比较时，产生冲突的概率约为2^-31，这是一个极小的值，所以算法中的check方法可以省略掉，Rabin-Karp算法的性能为线性级别，

内容总结

以上是互联网集市为您收集整理的《算法》笔记 15 - 子字符串查找全部内容，希望文章能够帮你解决《算法》笔记 15 - 子字符串查找所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/644696.html

来源：【匿名】

【上一篇】《算法》笔记 17 - 数据压缩【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【《算法》笔记 15 - 子字符串查找】教程文章相关的互联网学习教程文章

【算法题】字符串单词拆分【代码】

题目：给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。示例 2：输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释:...

字符串算法大全【代码】【图】

1、LCSdef lcs(a,b):lena=len(a)lenb=len(b)c=[[0 for i in range(lenb+1)] for j in range(lena+1)]flag=[[0 for i in range(lenb+1)] for j in range(lena+1)]for i in range(lena):for j in range(lenb):if a[i]==b[j]:c[i+1][j+1]=c[i][j]+1flag[i+1][j+1]=‘ok‘elif c[i+1][j]>c[i][j+1]:c[i+1][j+1]=c[i+1][j]flag[i+1][j+1]=‘left‘else:c[i+1][j+1]=c[i][j+1]flag[i+1][j+1]=‘up‘return c,flagdef printLcs(flag,a,i,j...

[PHP] 算法-字符串的左循环的PHP实现【代码】

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！ 1.字符串翻转,前n位取模长度,abc翻转成cba 后面的翻转成fedXYX ,然后再统一翻转 XYZdefabc 2.第二种思路,字符串复制一份拼接在一起,截取从n开始到le...

算法竞赛入门经典第3章数组和字符串学习笔记 2【代码】

蛇形填数蛇形填数：在n×n方阵里填入1，2，…，n×n，要求填成蛇形。例如，n＝4时方阵为： 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出。n≤8。这个肯定是要用到二维数组的用到了预判，先判断再向上下左右运动会不会越界以及将要运动到的地方是不是已经填了数#include<iostream> #include<cstring> #define maxn 20 using namespace std; int a[maxn][maxn]; int ...

字符串全排列和组合算法【代码】【图】

打印字符串的全排列算法的思路：把一个字符串分成两部分，第一个字符+后面部分所有的字符。这样就能够递归的求解整个过程了：1.每个字符都做一次首字符 2.当某个字符作为首字符的时候，求后面所有字符的全排列而这里的求后面所有字符的全排列可以看成递归的子问题全排列的递归树：但是这里还有一个问题，那就是字符串中有重复的字符时，这样的算法会增加最后的结果数目。比如说字符串aab，a+ab的全排列，然后交换还是a+ab的全排列...

poj 3617 Best Cow Line (字符串反转贪心算法)【代码】【图】

Best Cow LineTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 9284 Accepted: 2826DescriptionFJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year" competition. In this contest every farmer arranges his cows in a line and herds them past the judges.The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow...

代码练习（二维数组的定义，字符串加减，子元素的创建及绑定，排序算法）【代码】

<!DOCTYPE> <html><head><meta charset="utf-8"><title>IFE JavaScript Task 01</title></head> <body><ul id="source"><li>北京空气质量：90</li><li>上海空气质量：70</li><li>天津空气质量：80</li><li>广州空气质量：50</li><li>深圳空气质量：40</li><li>福州空气质量：32</li><li>成都空气质量：90</li></ul><ul id="resort"><!-- <li>第一名：北京空气质量：90</l...

boost字符串算法

boost::algorithm简介2007-12-08 16:59boost::algorithm提供了很多字符串算法，包括：大小写转换；去除无效字符；谓词；查找；删除/替换；切割；连接；我们用写例子的方式来了解boost::algorithm能够为我们做些什么。boost::algorithm学习#include <boost/algorithm/string.hpp>using namespace std;using namespace boost; 一：大小写转换1 to_upper() 将字符串转为大写Example:string str1(" hello world! ");to_upp...

字符串相似度算法，AS3实现，用于判断聊天广告【代码】

/*** 计算把source经过几个步骤可以转变到target的值 * @param source* @param target* @return * */publicstaticfunction editDistance(source:String,target:String):int{var slen:int = source.length;var tlen:int = target.length;var d:Array = [];for(var i:int=0;i<=slen;i++){d[i] = [];d[i][0] = i;if(i==0){for(var j:int=1;j<=tlen;j++){d[0][j] = j;}}else{for(var j:int=1;j<=tlen;j++){d[i][j] = 0;}}}for(var i:in...

ACM经典算法之字符串处理：字符串替换

语法：replace(char str[],char key[],char swap[]); 参数： str[]：在此源字符串进行替换操作 key[]：被替换的字符串，不能为空串 swap[]：替换的字符串，可以为空串，为空串表示在源字符中删除key[] 返回值：null 注意：默认str[]长度小于1000，如否，重新设定设定tmp大小需要 string.h 源程序：#include<stdio.h> #include<string.h>void replace(char str[],char key[],char swap[]) {int l1,l2,l3;int i,j;int flag;char tmp...

Levenshtein距离【编辑距离算法】字符串相似度算法

指两个字串之间，有一个转成另一个所需的最少编辑操作的次数。算法过程str1或str2的长度为0返回另一个字符串的长度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;初始化(n+1)*(m+1)的矩阵d，并让第一行和列的值从0开始增长。扫描两字符串（n*m级的），如果：str1[i] == str2[j]，用temp记录它，为0。否则temp记为1。然后在矩阵d[i,j]赋于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小...

字符串编码解压缩算法【图】

前几天，有一个学C的小伙伴和我交流一个问题，问题他是这么说的：传入一个字符串，格式要求如下：ep: A2D3B4C1D2那么将这个字符串解压的结果应为:AADDDBBBBCDD规则就是，必须满足，字符串的第一个是字母，可以大写也可以小写，第二个为数字，范围为1-9,解压的长度不得超过1000个字符。按照他的要求，我想了一下，实现了这个算法，算法如下:#include <stdio.h> #include <stdlib.h> #include <string.h>int main(void) {//char *str...

JAVA常见算法题(三十三)---求子串在字符串中出现的次数【代码】【图】

计算某字符串中子串出现的次数。publicstaticvoid main(String[] args) {String s1 = "adcdcjncdfbcdcdcd";String s2 = "cd";count(s1, s2);}publicstaticvoid count(String str1, String str2) {int count = 0;if (str1.equals("") || str2.equals("")) {System.out.println("你没有输入字符串或子串，无法比较！");//System.exit(0);} else {for (int i = 0; i <= str1.length() - str2.length(); i++) {if (str2.equals(str1.su...

1、串（字符串）以及串的模式匹配算法【代码】

串（或字符串）是由0个或多个字符组成的有限序列。0个字符的串成为空串。串中任意个连续的字符组成的子序列称为该串的子串。串的表示和实现串有3种机内表示方法：定长顺序存储表示，堆分配存储表示，串的块链存储表示。1、定长顺序存储表示：用一组地址连续的存储单元存储串值的字符序列。//--------串的定长顺序存储表示--------#define MAXSTRLEN 255 //用户可以在255以内定义最大串长 typedef unsigned char SString[MAXST...

python判断字符串是否是数字的算法【图】

判断字符串是否是数字（包含负数和小数）算法1：1、分小数和整数：如果小数点个数为1，则可能是小数。如小数点个数为0，则可能是整数。小数点个数非0也非1，那么就不是数字。2、如果是小数，再分正数和负数的情况：如果首位为负号，则可能是负小数。如果首位不为负号，则可能是正小数。 1）如果首位为负号，则去掉负号。 2）如果首位不为负号；或者是首位为负号，去掉首位负号之后。则判断是否为是否为“.”，如果是，那么就不是...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 《算法》笔记 15 - 子字符串查找

《算法》笔记 15 - 子字符串查找

内容导读

内容图文

暴力子字符串查找算法

隐式回退

性能

显式回退

Knuth-Morris-Pratt算法

确定有限状态自动机

DFA的构造

性能

Boyer-Moore算法

跳跃表的构建

性能

Rabin-Karp指纹字符串算法

关键思想

Horner方法

性能

内容总结

内容备注

内容手机端

【《算法》笔记 15 - 子字符串查找】教程文章相关的互联网学习教程文章

字符串 - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程