11.字符串

发表于 分类于 ， 本文字数： 1.2k

KMP模式匹配

KMP算法，又称模式匹配算法，能够在线性时间内判断一个字符串是否为另一个字符串的子串，并以此求出子串的出现位置。

1688128499849

1688128695536

1688128731324

求next数组:

1
2
3
4
5
6
7
8
next[1] = 0;

for (int i = 2, j = 0; i <= n; ++i)
{
    while (j > 0 && a[i] != a[j + 1]) j = next[j];//匹配j的下一个字符
    if (a[i] == a[j + 1]) ++j;
    next[i] = j;//有可能是 0
}

两者的定义相似，求法也相似。
求 f数组： 

1
2
3
4
5
6
7
8
9
10
11
12
//n指的是A串的长度
for (int i = 1, j = 0; i <= m; ++i)
{
    while (j > 0 && (j == n || b[i] != a[j + 1])) j = next[j];
    if (b[i] == a[j + 1]) ++j;
    f[i] == j;

    if (f[i] == n)
    {
        // do something（表明 a 在 b 中出现一次）
    }
}

整个算法的时间复杂度为Θ ( N + M )

在这里插入图片描述

在这里插入图片描述

字符串的最小表示

字符串长度为n，旋转n次，取字典序最小的那一种，即为字符串的最小表示。

例如：

s=”00ab”

变形有（省略引号）b00a ab00 0ab0

一共4种

那么找到其中字典序最小的一个，用的算法便是这个。

定义三个指针，i,j,k

初始i=0;j=1;k=0

首先，如果s[i]<s[j]那么很明显j++

如果s[i]>s[j]那么也很明显i=j++

省下的就是如果s[i]==s[j]的时候。

这时候有一个性质就是在i和j之间的所有的字符一定是大于等于s[i]的

另k=0，循环寻找第一个s[i+k]!=s[j+k]的位置

如果s[i+k]<s[j+k]那么j+=k+1

为什么呢？

首先s[i]到s[i+k-1]一定是大于等于s[i]，因为如果其中有一个数小于s[i]，那么这个数一定在s[j]到s[j+k-1]中存在，又因为必定有一个会在后面，所以如果s[j]先碰到了，那么一定不会继续到k的位置的，所以一定不存在比s[i]小的字符。

所以从其中的任意一个字符开始当作起始点，都不会比现在更小，所以只有从选出来的序列的后面那一个字符开始才有可能会是最小。

所以j+=k+1

如果序列中某个数和s[i]相等的话，那么一定会有之前或者以后再这个位置起始过，所以不需要再从这个位置进行起始。

因为在这里i和j是等价的，i在前和j在前的结果是一样的，所以i和j的处理是相同的，下面就不仔细的进行讲解了，直接贴代码：

还有就是如果i==j那么让j++就可以回到原先的状态了

最后的时候，肯定是小的不会动，而大的会不停的向后移动，所以最后只需要输出i和j最小的一个即可

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏