记录编号	380359	评测结果	AAAAAAAAAA
题目名称	[POJ3415]公共子串	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	1.657 s
提交时间	2017-03-09 06:23:04	内存使用	26.62 MiB

#include <stdio.h>
#include <ctime>
#include <algorithm>
#include <cstring>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdlib>
// #include <iostream>
#include <bitset>
#include <cmath>
#include <vector>
#define Mem(a, b) memset(a, b, sizeof a)
#define Mcpy(a, b) memcpy(a, b, sizeof a)
#define RG register
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;
IL void qkin(RG int &res){
	RG int x,f=1; RG char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;}
IL void read(RG int &A){ qkin(A); }
IL void read(RG int &A,RG int &B){ qkin(A),qkin(B); }
IL void read(RG int &A,RG int &B,RG int &C){ qkin(A),qkin(B),qkin(C); }
const double INF = 1e60;
const int inf = 0x7f7f7f7f;
const double Pi = acos(-1);
const double eps = 1e-8;
const int maxn = 100010*2;
LL size[maxn],sum[maxn];
int K,n,m,cnt,rt,last;
struct SAM
{
	int root,val,next[26];
}a[maxn];
void add(int c){
	int p = last, np = ++cnt;
	a[np].val = a[p].val + 1;
	while(p && !a[p].next[c]){
		a[p].next[c] = np;
		p = a[p].root;
	}
	if(!p) a[np].root = rt;
	else {
		int q = a[p].next[c];
		if(a[q].val == a[p].val+1) a[np].root = q;
		else {
			int nq = ++cnt;
			a[nq] = a[q];
			a[nq].val = a[p].val+1;
			a[np].root = a[q].root = nq;
			while(p && a[p].next[c] == q){
				a[p].next[c] = nq;
				p = a[p].root;
			}
		}
	}
	last = np;
}
int ws[maxn],rank[maxn];
char s1[maxn],s2[maxn];
LL ans;
void init(){
	cnt = 0;
	rt = last = ++cnt;
	ans = 0;
	Mem(a, 0);
	Mem(ws, 0);
	Mem(rank, 0);
	Mem(size, 0);
	Mem(sum, 0);
}
void solve(){
	init();
	scanf("%s%s", s1+1, s2+1);
	n = strlen(s1+1), m = strlen(s2+1);
	for(int i=1; i<=n; i++) add(s1[i]-'a');
	for(int i=1; i<=cnt; i++) ws[a[i].val]++;
	for(int i=1; i<=cnt; i++) ws[i] += ws[i-1];
	for(int i=cnt; i>=1; i--) rank[ws[a[i].val]--] = i;
	int p=rt;
	for(int i=1; i<=n; i++) size[p = a[p].next[s1[i]-'a']] = 1;
	for(int i=cnt; i>=1; i--) {
		int x = rank[i], fa = a[x].root;
		size[fa] += size[x];
	}	
	// for(int i=1; i<=cnt; i++){
	// 	printf("size[%d] = %d\n", i, size[i]);
	// }
	for(int i=1; i<=cnt; i++){
		int x = rank[i], fa = a[x].root;
		int l = a[a[fa].root].val+1, r = a[fa].val;
		if(r<K) continue;
		l = max(l, K);
		sum[x] += 1ll*(r-l+1)*size[fa] + sum[fa];
	}
	// for(int i=1; i<=cnt; i++){
	// 	printf("sum[%d] = %d\n", i, sum[i]);
	// }
	p = rt; int tmp = 0;
	for(int i=1; i<=m; i++){
		int x = s2[i] - 'a';
		if(a[p].next[x]){
			p = a[p].next[x];
			tmp++;
		} else {
			while(p && !a[p].next[x]) p = a[p].root;
			if(!p) tmp = 0, p = rt;
			else tmp = a[p].val + 1, p = a[p].next[x];			
		}
		if(tmp < K) continue;
		int l = max(K, a[a[p].root].val+1);
		ans += sum[p] + 1ll*(tmp - l + 1)*size[p];
	}
	printf("%lld\n", ans);
	return;
}
int main(){
#define HAHA LALA
#ifdef HAHA
	freopen("commonsubstrings.in", "r", stdin);
	freopen("commonsubstrings.out", "w", stdout);
#endif
	while(scanf("%d", &K), K) solve();
	return 0;
}