记录编号	163805	评测结果	AAAAAAAAAA
题目名称	[POJ3415]公共子串	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	3.139 s
提交时间	2015-05-26 17:22:57	内存使用	24.32 MiB

/****************************************\
* Author : ztx
* Title  : [cogs] 1712. [POJ3415]公共子串
* ALG    : SAM
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
	ret[0]=0;while (CH=getchar() , CH<'!') ;
	while (ret[++ret[0]]=CH,CH=getchar(),CH>'!') ;
	ret[ret[0]+1]=0;
}

#include <cstring>

#define  max(x,y) ((x)>(y)?(x):(y))

namespace Suffix_Automaton {
	#define  maxl  100010LL
	#define  maxt  200010LL
	#define  maxc  26LL
	struct SAM { int f,l,right,cnt,c[maxc]; } sam[maxt] ;
	int root = 1 , sink = 1 , tott = 1 , len = 0 ;
	inline void SAM_init() {
		memset(sam , 0 , sizeof sam) ;
		root = sink = tott = 1 ;
		len = 0 ;
	}
	inline void SAM_insert(int x) {
		int p , q , nq ;
		p = sink , sink = ++tott , len ++ ;
		sam[sink].l = sam[p].l+1 ;
		sam[sink].right = 1 ;
		for (; p && !sam[p].c[x] ; p=sam[p].f) sam[p].c[x] = sink ;
		if (!p) sam[sink].f = root ;
		else {
			q = sam[p].c[x] ;
			if (sam[p].l+1 == sam[q].l) sam[sink].f = q ;
			else {
				sam[nq=++tott] = sam[q] ;
				sam[nq].l = sam[p].l+1 ;
				sam[nq].right = 0 ;
				sam[q].f = sam[sink].f = nq ;
				for (; p && sam[p].c[x]==q ; p=sam[p].f) sam[p].c[x] = nq ;
			}
		}
	}
	int ws[maxt] = {0} , wv[maxl] = {0} ;
	inline void SAM_gr() {
		int i , p , fp ;
		Rep (i,1,len)  wv[i] = 0 ;
		Rep (i,1,tott) wv[sam[i].l] ++ ;
		Rep (i,1,len)  wv[i] += wv[i-1] ;
		Rep (i,1,tott) ws[wv[sam[i].l]--] = i ;
		Rev (i,tott,1) p = ws[i] , fp = sam[p].f , sam[fp].right += sam[p].right ;
	}
	#undef  maxl
	#undef  maxt
	#undef  maxc
}

using namespace Suffix_Automaton ;

int main() {
int K , x , i , p , fp , now ;
ll ans ;
	#define READ
	#ifdef  READ
		freopen("commonsubstrings.in" ,"r",stdin ) ;
		freopen("commonsubstrings.out","w",stdout) ;
	#endif
	while (read(K) , K) {
		SAM_init() ;
		while (CH=getchar(),CH<'!') ;
		while (SAM_insert(CH-'a'),CH=getchar(),CH>'!') ;
		SAM_gr() ;
		while (CH=getchar(),CH<'!') ;
		ans = 0 ;
		for (p = root , now = 0 ; CH>'!' ; CH=getchar()) {
			x = CH-'a' ;
			if (sam[p].c[x]) p = sam[p].c[x] , now ++ ;
			else {
				for ( ; p && !sam[p].c[x] ; p = sam[p].f) ;
				if (!p) now = 0 , p = root ;
				else now = sam[p].l+1 , p = sam[p].c[x] ;
			}
			fp = sam[p].f ;
			if (now >= K) {
				ans += (ll)(now-max(K,sam[fp].l+1)+1)*sam[p].right ;
				/* 第一次计算，只计算了LCS>=K时的情形，并在此时标记fp的cnt */
				if (K <= sam[fp].l) sam[fp].cnt ++ ;
			}
		}
		Rev (i,tott,1) {
			p = ws[i] , fp = sam[p].f ;
			ans += (ll)sam[p].cnt*(sam[p].l-max(K,sam[fp].l+1)+1)*sam[p].right ;
			/* 第二次计算，计算非LCS但符合要求的数量，topo计算cnt */
			if (K <= sam[fp].l) sam[fp].cnt += sam[p].cnt ;
		}
		printf("%lld\n", ans) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}