本文共 1324 字，大约阅读时间需要 4 分钟。

题目

解

比赛时最初是想到了 $O(n^3)$ 的打法， 可是 $n<=3000$ 我觉得不太行…

代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;string s1, s2;int f[4000][150], p2, p1, n, hash1, hash2, hash3;int b[100010][501];long long ans;int main(){   	scanf("%d", &n);	cin >> s1 >> s2;	s1 = " " + s1;	s2 = " " + s2;	for(int i = n-1; i; --i){   		for(int j = 97; j <= 123; ++j)  //预处理。f[i][j]为第i位后第一次出现j字母的位置			f[i][j] = f[i+1][j];		f[i][s1[i+1]] = i+1;	}	for(int i = 0; i < n; ++i){     //左端点		p2 = i+1; p1 = 1; hash1 = hash2 = hash3 = 0;		while(p2 <= n && p1 <= n){    //b串p2位于a串p1位匹配			while(s1[p1] != s2[p2] && p1) p1 = f[p1][s2[p2]]; //a串往后找  b串s2位的 这个字母			if(p1 == 0) break;  //没找到字母			hash1 = (hash1 * 131 + s2[p2]) % 100007;  //三重哈希			hash2 = (hash2 * 233 + s2[p2]) % 1333331;			hash3 = (hash3 * 199 + s2[p2]) % 49999;			for(int j = 1; j <= 499; j += 2){    //判断重复（底数开大！）				if(b[hash1][j] == 0){     //新出现					b[hash1][j] = hash2;					b[hash1][j+1] = hash3;					++ans;  //统计答案					break;				}				if(b[hash1][j] == hash2 && b[hash1][j+1] == hash3) break;			}			++p2; ++p1;		}	}	printf("%lld", ans);	return 0;}