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

本是古典何须时尚 2023-10-02 12:34 56阅读 0赞

题目描述：

> 给定一个串，如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。

样例输入：

6
    a
    ab
    abc
    abcd
    abcda
    abcdab

样例输出：

empty
    empty
    empty
    empty
    a
    ab

思路：

从长度为1开始查找真前后缀，分别比较p\[j\]和p\[p.length() - i + j\]

p[j] != p[p.length() - i + j]

实现代码：

#include<iostream>
    #include<string>
    using namespace std;
    
    int getlength(string p) {
    	int i = 1;
    	int num=0;
    	if (p.length() == 1) {
    		return 0;
    	}
    	while (i < p.length()) {
    		bool flag = true;
    		for (int j = 0; j < i; j++) {
    			if (p[j] != p[p.length() - i + j]) {
    				flag = false;
    			}
    		}
    		if (flag) {
    			num = i;
    		}
    		i++;
    	} 
    	return num;
    }
    
    string matched_Prefix_Postfix(string str) {
    	int* next = new int[100];
    	int num= getlength(str);
    	if (num==0) {
    		return string("empty");
    	}
    	else {
    		return string(str, 0, num);
    	}
    
    }
    
    int main() {
    	int n;
    	cin >> n;
    	while (n--) {
    		string s;
    		cin >> s;
    		cout << matched_Prefix_Postfix(s) << endl;
    	}
    	return 0;
    }