牛客多校I string

就是求所有的子串满足是的子串并且不存在子串使得子串和子串相同且子串的反串也不和相同。

首先我们考虑这个条件，这个条件说明和都是本质不同的子串。因此我们肯定是考虑求出串中本质不同的子串，然后想办法减掉这些本质不同的子串中，通过能够得到其他子串的一类子串的数量。想到这里，我们就可以把问题转换成求和的公共子串数量。但是考虑直接这么做有点困难，我们考虑转换一下问题，如果说一个子串能够通过反转得到中另外一个子串，那么我们可以肯定，该种串只能对应一种子串，那么我们考虑将连接到串后面，并且在中间添加特殊字符。那么对于新串，在串通过反串不能得到其他子串的一类子串可以形成的贡献，而对串中可以反转并且得到其他子串的一类子串的贡献只有,但是这样结果会少算，这个时候只需要加上回文串数量并且答案除就是结果。

//author Eterna
#define Hello the_cruel_world!
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
#include<cmath>
#include<climits>
#include<deque>
#include<functional>
#include<numeric>
#define max(x,y) ((x) > (y) ? (x) : (y))
#define min(x,y) ((x) < (y) ? (x) : (y))
#define ABS(x) ((x) >= 0 ? (x) : (-(x)))
#define pb(x) push_back(x)
#define lowbit(x) ((x) & (-(x)))
#define FRIN freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\in.txt", "r", stdin)
#define FROUT freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\out.txt", "w", stdout)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define outd(x) printf("%d\n", x)
#define outld(x) printf("%I64d\n", x)
#define memset0(arr) memset(arr, 0, sizeof(arr))
#define il inline
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 1e6;
const int INF = 0x7fffffff;
const int mod = 1e9 + 7;
const double eps = 1e-7;
const double Pi = acos(-1.0);
inline int read_int() {
    char c;
    int ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}
inline ll read_ll() {
    char c;
    ll ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}
struct SAM {
    struct node {
        int child[26], len, suf_link;
    }arr[2 * maxn + 5];
    int tot, last;
    void init() {
        for (int i = 0; i <= tot; ++i)memset0(arr[i].child), arr[i].len = arr[i].suf_link = 0;
        tot = last = 1;
    }
    void insert(char ch, int id) {
        int pos = last, now = ++tot;
        arr[now].len = arr[last].len + 1;
        while (pos && !arr[pos].child[ch - 'a']) {
            arr[pos].child[ch - 'a'] = now;
            pos = arr[pos].suf_link;
        }
        if (!pos)arr[now].suf_link = 1;
        else {
            int son = arr[pos].child[ch - 'a'];
            if (arr[son].len == arr[pos].len + 1) arr[now].suf_link = son;
            else {
                int rev = ++tot;
                arr[rev] = arr[son];
                arr[rev].len = arr[pos].len + 1;
                arr[son].suf_link = arr[now].suf_link = rev;
                while (pos && arr[pos].child[ch - 'a'] == son) {
                    arr[pos].child[ch - 'a'] = rev;
                    pos = arr[pos].suf_link;
                }
            }
        }
        last = now;
    }
};
SAM sam;
struct PAM {
    struct node {
        int child[26], cnt, fail, num, len;
    }arr[maxn + 5];
    int last, n, tot;
    char s[maxn + 5];
    il void clear() {
        for (int i = 0; i <= tot; ++i) {
            memset0(arr[i].child);
            arr[i].cnt = arr[i].fail = arr[i].len = arr[i].num = 0;
        }
        last = n = 0;
        s[0] = '#';
        arr[0].fail = 1, arr[1].len = -1;
        tot = 1;
    }
    il int find_fail(int x) {
        while (s[n - arr[x].len - 1] != s[n])x = arr[x].fail;
        return x;
    }
    il void add(char c) {
        s[++n] = c;
        int cur = find_fail(last);
        if (!arr[cur].child[c - 'a']) {
            int now = ++tot;
            arr[now].len = arr[cur].len + 2;
            int p = find_fail(arr[cur].fail);
            arr[now].fail = arr[p].child[c - 'a'];
            arr[cur].child[c - 'a'] = now;
            arr[now].num = arr[arr[now].fail].num + 1;
        }
        last = arr[cur].child[c - 'a'];
        ++arr[last].cnt;
    }
    il void count() { for (int i = tot; i >= 0; --i)arr[arr[i].fail].cnt += arr[i].cnt; }
}pam;
char s[maxn + 5];
ll res;
int n;
int main()
{
    scanf("%s", s + 1);
    sam.init();
    pam.clear();
    n = strlen(s + 1);
    for (int i = 1; i <= n; ++i)sam.insert(s[i], i);
    for (int i = 1; i <= n; ++i)pam.add(s[i]);
    pam.count();
    sam.insert('#', n + 1);
    for (int i = n; i > 0; --i)sam.insert(s[i], i + n + 1);
    for (int i = 2; i <= sam.tot; ++i)res += sam.arr[i].len - sam.arr[sam.arr[i].suf_link].len;
    res -= 1ll * (n + 1) * (n + 1);
    res += pam.tot - 1;
    cout << res / 2 << endl;
    //system("pause");
    return 0;
}