相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4566
解题报告
我们可以拿一个串建SAM,把另一个串扔到SAM中匹配一遍
也可以直接把两个串拼一起,然后建SAM,最后遍历一下就好
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 800009; const int SGZ = 27; int n, m; char s[N]; class Suffix_Automaton{ int cnt, tail, ch[N][SGZ], fail[N], sz[N][2], len[N], head[N], nxt[N], to[N]; public: inline void init() { cnt = tail = 1; for (int i = 1; i <= n; i++) { append(s[i] - 'a', 0); } append(SGZ - 1, -1); for (int i = n + 2; i <= n + m + 1; i++) { append(s[i] - 'a', 1); } for (int i = 1; i <= cnt; i++) { AddEdge(fail[i], i); } DFS(0, 0); } inline LL query() { LL ret = 0; for (int i = 1; i <= cnt; i++) { ret += (LL)(len[i] - len[fail[i]]) * sz[i][0] * sz[i][1]; } return ret; } private: inline void DFS(int w, int f) { for (int i = head[w]; i; i = nxt[i]) { if (to[i] != f) { DFS(to[i], w); sz[w][0] += sz[to[i]][0]; sz[w][1] += sz[to[i]][1]; } } } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } inline void append(char cc, int t) { int w = tail, cur = ++cnt; if (t != -1) { sz[cur][t] += 1; } len[cur] = len[tail] + 1; for (tail = cur; w && !ch[w][cc]; ch[w][cc] = cur, w = fail[w]); if (w) { if (len[ch[w][cc]] == len[w] + 1) { fail[cur] = ch[w][cc]; } else { int nt = ++cnt, pt = ch[w][cc]; memcpy(ch[nt], ch[pt], sizeof(ch[nt])); len[nt] = len[w] + 1; fail[nt] = fail[pt]; fail[cur] = fail[pt] = nt; for (; w && ch[w][cc] == pt; ch[w][cc] = nt, w = fail[w]); } } else { fail[cur] = 1; } } }sam; int main() { scanf("%s", s + 1); n = strlen(s + 1); s[n + 1] = 'z' + 1; scanf("%s", s + n + 2); m = strlen(s + n + 2); sam.init(); printf("%lld\n", sam.query()); return 0; }
I think this is a real great post.
I like what you guys are up too. Such clever work and reporting! Keep up the excellent works guys I’ve incorporated you guys to my blogroll. I think it will improve the value of my web site :).
968201 52102Wohh exactly what I was looking for, appreciate it for posting . 400173
980713 12363What would you recommend about your publish that you just made a few days ago? Any certain? 162043
312173 628895What platform and theme are you making use of if I may possibly ask? Exactly where can I buy them? x 15111
574635 414274I observe there can be a lot of spam on this weblog. Do you want assist cleaning them up? I might assist in between courses! 379809
191216 121510hey there i stumbled upon your website searching about the internet. I wanted to say I enjoy the appear of points around here. Maintain it up will save for certain. 694952
940302 237596But wanna comment that you have a quite nice internet site , I adore the style and style it really stands out. 43085
279115 984667Extremely man or woman speeches want to seat giving observe into couples. Brand new sound system just before unnecessary folks ought to always be mindful of typically senior general rule from public speaking, which is to be the mini. finest man speaches 353585
232883 206890A really exciting go via, I could not agree completely, but you do make some really legitimate factors. 475791
141050 281775Im having just a little issue I cant subscribe your feed, Im utilizing google reader fyi. 657875
21938 871106As soon as I identified this internet internet site I went on reddit to share some of the enjoy with them. 172139
515510 963954I actually enjoy examining on this internet site , it has got excellent posts . 182381
452643 128140Quite informative and excellent complex body part of articles , now thats user pleasant (:. 212913
Very well written post. It will be beneficial to everyone who usess it, including me. Keep doing what you are doing – i will definitely read more posts.