Passward

xiaoxiao2021-02-28  6

题面

  题目描述

  你来到了一个庙前,庙牌上有一个仅包含小写字母的字符串 s。

  传说打开庙门的密码是这个字符串的一个子串 t,并且 t 既是 s 的前缀又是 s 的后缀并且还在 s 的中间位置出现过一次。

  如果存在这样的串,请你输出这个串,如有多个满足条件的串,输出最长的那一个。

  如果不存在这样的串,输出”Just a legend”(去掉引号)。

  输入格式:

  仅一行,字符串 s。

  输出格式:

  如题所述

  样例输入

  fixprefixsuffix

  样例输出:

  fix

  数据范围:

  对于 60%的数据,1 s 的长度 100

  对于 100%的数据,1 s 的长度 100000


思路

  考场想出下面这个算法,时间复杂度什么的都没有保证。但数据都很水, 所以大胆搜索。

  先定义结构体,num为原数组下标, step为当前以此下标匹配成功的长度。

struct Step { int num; int step; }tmp;

  b数组维护值为首字母的位置的下标:

for (int i = 0;i < y;i ++) if (ch[x] == ch[i]) b.push(Step{i, 0});

  若队列大小小于2,则必无解:

if (b.size() <= 2) { printf("Just a legend"); return 0; }

  然后每次将匹配长度向后推进一个,比较判断此时队列中所有元素是否仍然可行;将可行解再push进队列:

while (b.size() >= 3) { tmpb = b.front(); b.pop(); if (tmpb.step >= now) now ++; if (ch[tmpb.num + now - 1] == ch[x + now - 1]) { b.push(Step{tmpb.num, now}); if (tmpb.num + now - 1 == y - 1 && b.size() >= 3) ans = max(ans, now); } }

  这里可以更新答案:若此时的匹配存在已经匹配到末位的元素(因为从首位开始匹配,所以匹配到末位一定为原串的后缀)并且当前已经匹配成功的元素,那么就将答案更新为此元素的step:

if (ch[tmpb.num + now - 1] == ch[x + now - 1]) { b.push(Step{tmpb.num, now}); if (tmpb.num + now - 1 == y - 1 && b.size() >= 3) ans = max(ans, now); }

  如果结果未被更新,便无解:

if (ans == -1) { printf("Just a legend"); return ; }

  其实听说正解为KMP,但考场实测24MS,只比KMP慢8MS。

但其实还是很好构造出卡这个算法的数据。 如若有一连串的“aaaaaaaaaaaaaaaaaaa”,那每次都会只否定一组,接近 Θ(n2) 的时间复杂度。

代码

#include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> #include <iostream> #define LL long long using namespace std; const size_t MN = 100005; struct Step { int num; int step; }tmp; char ch[MN]; int x, y; queue < Step > b; void solve() { Step tmpb; int now = 0, ans = -1; while (b.size() >= 3) { tmpb = b.front(); b.pop(); if (tmpb.step >= now) now ++; if (ch[tmpb.num + now - 1] == ch[x + now - 1]) { b.push(Step{tmpb.num, now}); if (tmpb.num + now - 1 == y - 1 && b.size() >= 3) ans = max(ans, now); } } if (ans == -1) { printf("Just a legend"); return ; } for (int i = 0;i < ans;i ++) putchar(ch[i]); } int main() { scanf("%s", ch); y = strlen(ch); if (y <= 2) { printf("Just a legend"); return 0; } tmp.step = 1; for (int i = 0;i < y;i ++) { if (ch[x] == ch[i]) b.push(Step{i, 0}); } if (b.size() <= 2) { printf("Just a legend"); return 0; } solve(); return 0; }
转载请注明原文地址: https://www.6miu.com/read-200156.html

最新回复(0)