C – Cornelia Street

题意：

给出一个字符串，该字符串由两个长度相等的字符串A B组成，组成规则是 AA…AABB…BBAA…a, 也就是n个A，m个B，k个A，再加上一个A的前缀a，其中n，m，k > 0，数量不知道，0<=a的长度<=|A|，你需要输出A和B，如果有多种答案，输出长度最短的

思路：

哈希预处理，然后去枚举长度，用一个vector存该长度下每一段的不同的哈希值，暂时不需要管那个a，只有vector的长度等于3，且v[0] = v[2],也就是前面的A等于后面的A时，再判断一下那个a是不是A的前缀即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef unsigned long long ull;
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 800000 + 50
int n, m;
int tr[MAX];

char s[MAX];
ull base = 31;
ull hhash[MAX],mul[MAX];
void init()
{
    mul[0]=1;hhash[0]=0;
    for(int i=1;i<=n;i++)
        mul[i]=mul[i-1]*base;
    for(int i=1;i<=n;i++)
        hhash[i]=hhash[i-1]*base+s[i];
}
ull getHash(int l,int r)
{
    return hhash[r]-hhash[l-1]*mul[r-l+1];
}

void work(){
    scanf("%s",s+1);
    n=(int)strlen(s+1);
    init();
    int k = 0;
    for(int len = 1; len <= n / 3; ++len){
        vector<ull>v;v.push_back(getHash(1, len));
        for(int j = 1; j <= n - len + 1; j += len){
            ull p = getHash(j, j + len - 1);
            if(p != v.back()){
                v.push_back(p);
                if(v.size() == 2)k = j;
            }
            if(v.size() > 3){
                break;
            }
        }
        if(v.size() == 3 && v[0] == v[2] && getHash(1, n % len) == getHash(n - (n % len) + 1, n)){
            for(int j = 1; j <= len; ++j){
                cout << s[j];
            }
            cout << ' ';
            for(int j = k; j <= k + len - 1; ++j){
                cout << s[j];
            }
            cout << endl;
            return;
        }
    }
    
}


int main(){
    work();
    return 0;
}