题意：给出一个字符串，要把它折分成三部分 a、b、c ， 使得 a+b=c 。输出任何一种可行情况。

tags：字符串 hash

因为 a+b=c ，所以 lena、lenb 至少要有一个等于 lenc 或 lenc-1  。所以枚举 lenc，每次检验一下可不可行。

但每次都暴力检验肯定超时，这里把字符串hash 一下，根据 hash值 快速检验。

 

记一下模板：

const int mod = 1e9+7;ll  Hash[N], p[N], Base=10;void Init(string si){    int len = si.size();    Hash[0]=0;    for(int i=0; i

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 1000005;const int mod = 1e9+7;ll  Hash[N], p[N], Base=10;void Init(string si){    int len = si.size();    Hash[0]=0;    for(int i=0; i
       
        =10) a3-=10, flag=1;        else flag=0;        if(a3!=s3[len3-(lena-i)]-'0') return false;    }    return true;}bool solve(int lena, int lenb){    if(lena>lenc || lenb>lenc) return false;    if(lena<0 || lenb<0) return false;    if(si[lena]=='0' && lenb!=1) return false;    if(si[lena+lenb]=='0' && len-lena-lenb!=1) return false;    if( (get(1,lena)+get(lena+1, lena+lenb))%mod != get(lena+lenb+1, len) ) return false;    //return true;    return  check(lena, lenb);}int main(){    cin>>si;    Init(si);    len=si.size();    for(lenc=1; lenc<=len-2; ++lenc)    {        if(solve(lenc, len-lenc*2)) {            print(lenc, len-lenc*2); return 0;        }        if(solve(lenc-1, len-lenc-(lenc-1))) {            print(lenc-1, len-lenc-(lenc-1)); return 0;        }        if(solve(len-lenc*2, lenc)) {            print(len-lenc*2, lenc); return 0;        }        if(solve(len-lenc-(lenc-1), lenc-1)) {            print(len-lenc-(lenc-1), lenc-1); return 0;        }    }    return 0;}