题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6646
题意为求$a*10^{x}+b*10^{y}=c*10^{z}$满足公式的任意一组解$x,y,z$。
因为c有可能会由$a+b$进位得到，所以先在c后添加0使得c长度最长，然后先固定a的长度为c-1或c,遍历b的长度为b到c。
用hash判断是否相等。再交换b和a的顺序再判断一次。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
struct hash {
int base, mod;
int tot, Hash[maxn], xp[maxn];
hash() {
tot = ; xp[] = ; base = ; mod = 1e9 + ;
}
void init() { tot = ; }
void insert(int c) {
tot++;
Hash[tot] = (1LL * Hash[tot - ] * base + c) % mod;
xp[tot] = (1LL * xp[tot - ] * base) % mod;
}
int query(int l, int r) {
if (l == ) return Hash[r];
return (Hash[r] - (1LL * Hash[l - ] * xp[r - l + ] % mod) + mod) % mod;
}
friend bool check(hash &a, int l1, int r1, hash &b, int l2, int r2, hash &c, int l3, int r3) {
if ((a.query(l1, r1) + b.query(l2, r2)) % a.mod != c.query(l3, r3)) return false;
return true;
} }h[];
char a[][maxn];
int len[], oldlen[];
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%s%s%s", a[] + , a[] + , a[] + );
for (int i = ; i <= ; i++)
oldlen[i] = len[i] = strlen(a[i] + ), h[i].init();
for (int i = ; i <= ; i++)
for (int j = ; j <= len[i]; j++)
h[i].insert(a[i][j] - '');
int x = , y = , z = ;
while (len[] <= max(len[], len[]) + ) {
z++;
a[][++len[]] = '';
h[].insert();
}
while (len[] < len[]) {
a[][++len[]] = '';
h[].insert();
}
while (len[] < len[]) {
a[][++len[]] = '';
h[].insert();
}
int f = ;
for (int i = oldlen[]; i <= len[] && f; i++) {
if (check(h[], , i, h[], , len[] - , h[], , len[])) {
f = ;
x = i - oldlen[], y = len[] - - oldlen[];
break;
}
if (check(h[], , i, h[], , len[], h[], , len[])) {
f = ;
x = i - oldlen[], y = len[] - oldlen[];
break;
}
}
for (int i = oldlen[]; i <= len[] && f; i++) {
if (check(h[], , len[] - , h[], , i, h[], , len[])) {
f = ;
x = len[] - - oldlen[], y = i - oldlen[];
break;
}
if (check(h[], , len[], h[], , i, h[], , len[])) {
f = ;
x = len[] - oldlen[], y = i - oldlen[];
break;
}
}
if (f)
printf("-1\n");
else
printf("%d %d %d\n", x, y, z);
}
}