思路是枚举矩阵列数，然后将字符矩阵转换成字符串，通过字符数组求不同子串数目。最后，减去不成立的情况。使用特殊字符分割可能的组合。
/* 4029 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxr = ;
const int maxn = 2e5+;
const int base = ;
map<int,int> tb;
int a[maxn*];
int height[maxn], rrank[maxn], sa[maxn*];
int wa[maxn], wb[maxn], wc[maxn], wv[maxn];
char s[maxr][maxr];
int H[maxr][maxr];
int r, c; bool c0(int *r, int a, int b) {
return r[a]==r[b] && r[a+]==r[b+] && r[a+]==r[b+];
} bool c12(int k, int *r, int a, int b) {
if (k == )
return r[a]<r[b] || (r[a]==r[b] && c12(, r, a+, b+));
else
return r[a]<r[b] || (r[a]==r[b] && wv[a+]<wv[b+]);
} void sort(int *r, int *a, int *b, int n, int m) {
int i; for (i=; i<n; ++i) wv[i] = r[a[i]];
for (i=; i<m; ++i) wc[i] = ;
for (i=; i<n; ++i) wc[wv[i]]++;
for (i=; i<m; ++i) wc[i] += wc[i-];
for (i=n-; i>=; --i) b[--wc[wv[i]]] = a[i];
} #define F(x) ((x)/3 + ((x)%3==1 ? 0:tb))
#define G(x) ((x)<tb ? (x)*3+1 : ((x)-tb)*3+2)
void dc3(int *r, int *sa, int n, int m) {
int i, j, *rn=r+n, *san=sa+n, ta=, tb=(n+)/, tbc=, p; r[n] = r[n+] = ;
for (i=; i<n; ++i) if (i%!=) wa[tbc++] = i;
sort(r+, wa, wb, tbc, m);
sort(r+, wb, wa, tbc, m);
sort(r, wa, wb, tbc, m);
for (p=, rn[F(wb[])]=, i=; i<tbc; ++i)
rn[F(wb[i])] = c0(r, wb[i-], wb[i]) ? p- : p++;
if (p < tbc)
dc3(rn, san, tbc, p);
else
for (i=; i<tbc; ++i) san[rn[i]] = i;
for (i=; i<tbc; ++i)
if (san[i] < tb)
wb[ta++] = san[i] * ;
if (n% == )
wb[ta++] = n - ;
sort(r, wb, wa, ta, m);
for (i=; i<tbc; ++i) wv[wb[i]=G(san[i])] = i;
for (i=,j=,p=; i<ta && j<tbc; ++p)
sa[p] = c12(wb[j]%, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
while (i < ta) sa[p++] = wa[i++];
while (j < tbc) sa[p++] = wb[j++];
} void calheight(int *r, int *sa, int n) {
int i, j, k = ; for (i=; i<=n; ++i) rrank[sa[i]] = i;
for (i=; i<n; height[rrank[i++]]=k)
for (k?k--:, j=sa[rrank[i]-]; r[j+k]==r[i+k]; ++k) ;
} void printSa(int n) {
for (int i=; i<=n; ++i)
printf("%d ", sa[i]);
putchar('\n');
} void printHeight(int n) {
for (int i=; i<=n; ++i)
printf("%d ", height[i]);
putchar('\n');
} void solve() {
__int64 ans = , tot, tmp;
int n = ; memset(H, , sizeof(H));
rep(w, , c+) {
tb.clr();
int cn = c - w + ;
int cnt = cn + ;
int sidx = ; rep(i, , r) {
rep(j, , cn) {
H[i][j] = H[i][j] * base + s[i][j+w-]-'A';
if (tb.find(H[i][j]) == tb.end())
tb[H[i][j]] = cnt++;
}
} n = ;
rep(j, , cn) {
rep(i, , r)
a[n++] = tb[H[i][j]];
a[n++] = sidx++;
}
a[n] = ; dc3(a, sa, n+, cnt+);
calheight(a, sa, n); tot = ;
rep(i, , n+)
tot += (n - sa[i] - height[i]); tmp = n;
rep(i, , cn) {
tmp -= r;
tot -= (r+) * tmp;
--tmp;
} ans += tot;
} printf("%I64d\n", ans);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t; scanf("%d", &t);
rep(tt, , t+) {
scanf("%d %d", &r, &c);
rep(i, , r)
scanf("%s", s[i]);
printf("Case #%d: ", tt);
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
数据生成器。
from random import randint, shuffle
import shutil
import string def GenDataIn():
with open("data.in", "w") as fout:
t = 20
uc = list(string.uppercase)
fout.write("%d\n" % (t))
for tt in xrange(t):
n = randint(20, 50)
m = randint(20, 50)
fout.write("%d %d\n" % (n, m))
for i in xrange(n):
line = ""
for j in xrange(m):
idx = randint(0, 25)
line += uc[idx]
fout.write("%s\n" % (line)) def MovDataIn():
desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
shutil.copyfile("data.in", desFileName) if __name__ == "__main__":
GenDataIn()
MovDataIn()