题解 P6739 【[BalticOI 2014 Day1] Three Friends】

· · 题解

看了下题解，全是哈希。

这里写一个更简单的做法。

思路

由题意可知 N 得为奇数，S 才存在，所以先特判 N 为偶数的情况。

由题意可知 S 的长度为 \lfloor \dfrac {N}{2}\rfloor， 设 S 的长度为 M。

因为只插入一个字符，所以如果存在 S，则 U 的前 M 个字符或后 M 个字符中一定有一边是 S。

所以可以用 substr 函数分别截取前 M 个字符和后 M 个字符，再依次匹配检查是否合法。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, a1, a2;
string u, s1, s2;

int main()
{
    scanf("%d", &n);
    if (n % 2 == 0)
    {
        printf("NOT POSSIBLE\n");
        return 0;
    }
    cin >> u;
    m = n / 2;

    s1 = u.substr(0, m); //匹配检查前M个字符
    int j = 0;
    for (int i = m; i < n && j < m; i++) 
        if (u[i] == s1[j]) j++;
    if (j == m) a1 = 1;

    s2 = u.substr(n - m, m); //匹配检查后M个字符
    j = 0;
    for (int i = 0; i < n - m && j < m; i++)
        if (u[i] == s2[j]) j++;
    if (j == m) a2 = 1;

    if (!a1 && !a2) printf("NOT POSSIBLE\n");
    else if (a1 && a2 && s1 != s2) printf("NOT UNIQUE\n");
    else if (a1) cout << s1 << endl;
        else cout << s2 << endl;
    return 0;
}