5.8 单调栈 & 悬线法 & 相关的题（和 dp 也多少沾点）

今日小题：一个 CF div2 的 A 的签到题，记录一下这个做法：

求一个字符串的最长非回文字符串：无解：长度为 1 或整个串每个字符都一样；有解：判断这个串是不是回文，如果不是，输出长度，如果是输出长度 - 1。感觉非常妙。不写证明，感觉非常好想...

#include<bits/stdc++.h>
using namespace std;
int T;
string s;
void finish()
{
    cin >> s;
    int len = s.size();
    int flag = 0;
    for(int i = 1; i < len; i ++ ) if(s[i] != s[i - 1]) {flag = 1;break;}
    if(! flag || len == 1)
    {
        printf("-1\n");
        return;
    }
    int i = 0, j = len - 1;
    while(i < j)
    {
        if(s[i] == s[j]) {i ++;j --;}
        else {flag = 0;break;}
    }
    if(! flag) printf("%d\n", len);
    else printf("%d\n", len - 1);
}
int main()
{
    scanf("%d", &T);
    while(T -- ) finish();
    return 0;
}

引入：用两个和这个没啥关系但可以思考的题引导。

P1387 最大正方形