串应用- 计算一个串的最长的真前后缀

叶茂林

发布于 2023-07-30 11:46:42

1660

发布于 2023-07-30 11:46:42

题目描述

给定一个串，如ABCDAB，则ABCDAB的真前缀有：{ A, AB,ABC, ABCD, ABCDA }ABCDAB的真后缀有：{ B, AB,DAB, CDAB, BCDAB } 因此，该串的真前缀和真后缀中最长的相等串为AB，我们称之为该串的“最长的真前后缀”。试实现一个函数string matched_Prefix_Postfix(string str)，得到输入串str的最长的真前后缀。若不存在最长的真前后缀则输出empty

输入

第1行：串的个数 n第2行到第n+1行：n个字符串

输出

n个最长的真前后缀，若不存在最长的真前后缀则输出empty。

输入样例1

6 a ab abc abcd abcda abcdab

输出样例1

empty empty empty empty a ab

思路分析

KMP算法不仅仅可以用了求子串，它的next值有着非常丰富的应用。

我们首先来求next的值，下标从1开始的话，next【0】存的是子串的长度，下一个next值需要根据前一个next值来确定，首先判断当前字符的前面所组成的字符串的前后缀（前一个字符和第一个字符）是否是相同的字符，如果相同，那么当前字符的next值为前一个next值+1，如果不同，继续比较前一个字符和前一个next值所对应的字符是否相同，如果都不相同，那么next值为1。

但是看代码可以知道，我们拓展了字符串，这是因为要求出最后一个字符对应的next值。

字符串的最长的真前后缀就是从第一个字符串开始连续最后一个next值数目（下标从0开始，下标从1开始需要减1）的子串。

AC代码

#include <bits/stdc++.h>

using namespace std;

string matched_Prefix_Postfix(string str) {
    str+='#';
    int next[str.size() + 1];
    next[0] = str.size();
    next[1] = 0;
    int i = 2, j = 0;
    while (i <= next[0]) {
        if (j == 0 || str[i - 2] == str[j - 1]) {
            next[i] = j + 1;
            i++;
            j = next[i - 1];
        } else j = next[j];
    }
    if (next[str.size()] <= 1)
        return "";
    return str.substr(0, next[str.size()]-1);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string str;
        cin >> str;
        if (matched_Prefix_Postfix(str) != "")cout << matched_Prefix_Postfix(str) << endl;
        else cout << "empty" << endl;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除

size