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

简介: 这篇文章提供了一个C++程序,用于找出给定字符串的最长真前后缀,并展示了如何通过计算每个子串的最长相同前后缀来实现这一功能。

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

Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 36     Solved: 24

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

题目描述

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

ac代码如下:

#include<iostream>
using namespace std;

int Get_next(string a)
{
    int i=0,k=-1;
    int len=a.length(),maxn=0;
    int *nextt=new int[a.length()+1];
    nextt[0]=-1;
    while(i<len)
    {
        if(k==-1||a[i]==a[k])
        {
            i++,k++;
            nextt[i]=k;
            if(k*2<=i)maxn=max(maxn,k);
            if(i/(i-k)%2==0)maxn=max(maxn,(i-k)*(i/(i-k)/2));
        }
        else k=nextt[k];
    }

    return maxn;
}
int get_maxnum(string a)
{
    int len=a.length(),maxn=0;
    for(int i=0;i<len;i++)
    {
        maxn=max(maxn,Get_next(a.substr(i,len)));
    }
    return maxn;
}
int main()
{
    string a;
    int n;
    cin>>n;
    while(n--)
    {
    cin>>a;
    int num=get_maxnum(a);
    if(!num)cout<<-1<<endl;
    else cout<<num<<endl;
    }
    return 0;
}
相关文章
|
8月前
|
存储
【字符串】最长不含重复字符的子字符串
【字符串】最长不含重复字符的子字符串
|
C语言
带你快速了解字符(串)函数(一)
带你快速了解字符(串)函数(一)
带你快速了解字符(串)函数(二)
带你快速了解字符(串)函数(二)
|
8月前
|
算法 测试技术 C#
【前缀和】3085. 成为 K 特殊字符串需要删除的最少字符数
【前缀和】3085. 成为 K 特殊字符串需要删除的最少字符数
带你快速了解字符(串)函数(三)
带你快速了解字符(串)函数(三)
|
8月前
leetcode-1784:检查二进制字符串字段
leetcode-1784:检查二进制字符串字段
37 0
|
算法
【Day20】LeetCode算法题【1784. 检查二进制字符串字段】【14. 最长公共前缀】
了解LeetCode算法题【1784. 检查二进制字符串字段】。
121 0
【Day20】LeetCode算法题【1784. 检查二进制字符串字段】【14. 最长公共前缀】
|
测试技术
字符串中有多少个不重复的字符并按由前到后的顺序输出一个新的字符串和该字符串长度的整数
字符串中有多少个不重复的字符并按由前到后的顺序输出一个新的字符串和该字符串长度的整数
97 0