木易

# Road Map

# 字符串处理

字符串处理题目特点

  • 题目难度一般不会很高，主要考察细节
  • 注意是否越界

# 常用代码模板

# 查找下一个不相等的字符

找到第一个 s[j] != s[i] 或者 j==n

双指针的思想

while (j < s.size() && s[j]==s[i]) j++;
1

# KMP 算法

输入样例：
3
aba
5
ababa
输出样例：
0 2
1
2
3
4
5
6
7

代码实现

const int N = 10010, M = 100010;
int n, m;
int ne[N];
char s[M], p[N]; // s: 模式串；t: 模板串

int main() {
    cin >> n >> p + 1 >> m >> s + 1;
    for (int i = 2, j = 0; i <= n; i ++ ){
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ ) {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n){
            printf("%d ", i - n);
            j = ne[j];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 题目

← 0x15x01_字符串匹配 →