自己yy的方法yyyyyyyy着就A了，写篇博客庆祝一下。

题目：

分析：

SAM（可能是）模板题（不会SAM的同学戳我：【知识总结】后缀自动机的构建）。

对\(s1\)建出SAM，用\(s2\)在上面跑。用\(size[i]\)表示结点\(i\)的\(Right\)集合大小（直接拓扑排序后DP就行）。既然要求\(s2\)中有多少子串在\(s1\)中出现了，那么用\(f[i]\)表示结点\(i\)对应的所有子串在\(s2\)中一共出现了多少次（位置不同算多次）。答案就是\(\sum f[i]\cdot size[i]\)

如何计算\(f[i]\)呢？如果当前匹配过程中走到了\(p\)点，匹配长度为\(len\)。很明显，当前匹配到的是从\(p\)点沿着\(fa\)链到根的路径上对应的长度不大于\(len\)的字符串。它对\(f[p]\)有\(len-min[p]+1=len-max[fa[p]]\)的贡献（SAM上\(min[p]-1=max[fa[p]]\)），且对这条路径上任意一点\(q\)的\(f[q]\)都有\(max[q]-min[q]+1=max[q]-max[fa[q]]\)的贡献。可以发现此时只有对\(f[p]\)的贡献与\(len\)有关，对其他结点\(q\)的贡献只取决于\(q\)在\(fa\)树上的子树的访问次数之和（乘上\(max[q]-max[fa[q]]\)）。所以这里只处理对\(f[p]\)的贡献，并记录一下\(p\)被访问了多少次，处理完后一起推上去就行了（类似树上差分）。时间复杂度\(O(n)\)。这里可能讲得不清楚，详见代码qwq。

代码：

还是比较好写的。别问我Auto_Suffix_Chicken是什么东西

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cctype>

#include <string>

#undef i

#undef j

#undef k

#undef true

#undef false

#undef min

#undef max

#undef sort

#undef swap

#undef if

#undef for

#undef while

#undef printf

#undef scanf

#undef putchar

#undef getchar

#define _ 0

using namespace std;

namespace zyt

{

	const int N = 2e5 + 10;

	template<typename T>

	inline bool read(T &x)

	{

		bool f = false;

		char c;

		x = 0;

		do

			c = getchar();

		while (c != EOF && c != '-' && !isdigit(c));

		if (c == EOF)

			return false;

		if (c == '-')

			f = true, c = getchar();

		do

			x = x * 10 + c - '0', c = getchar();

		while (isdigit(c));

		if (f)

			x = -x;

		return true;

	}

	inline bool read(string &s)

	{

		static char buf[N];

		if (scanf("%s", buf) == -1)

			return false;

		s = buf;

		return true;

	}

	template<typename T>

	inline void write(T x)

	{

		static char buf[20];

		char *pos = buf;

		if (x < 0)

			putchar('-'), x = -x;

		do

			*pos++ = x % 10 + '0';

		while (x /= 10);

		while (pos > buf)

			putchar(*--pos);

	}

	const int CH = 26;

	typedef long long ll;

	string s1, s2;

	namespace Auto_Suffix_Chicken

	{

		struct node

		{

			int size, max, fa, s[CH];

		}tree[N << 1];

		int len, cnt, last;

		inline void init()

		{

			cnt = last = 1;

		}

		inline int ctoi(const char c)

		{

			return c - 'a';

		}

		void insert(const char c)

		{

			int x = ctoi(c), np = ++cnt, p = last;

			tree[np].max = tree[p].max + 1;

			tree[np].size = 1;

			while (p && !tree[p].s[x])

				tree[p].s[x] = np, p = tree[p].fa;

			if (!p)

				tree[np].fa = 1;

			else

			{

				int q = tree[p].s[x];

				if (tree[p].max + 1 == tree[q].max)

					tree[np].fa = q;

				else

				{

					int nq = ++cnt;

					memcpy(tree[nq].s, tree[q].s, sizeof(char[CH]));

					tree[nq].max = tree[p].max + 1;

					tree[nq].fa = tree[q].fa;

					tree[np].fa = tree[q].fa = nq;

					while (p && tree[p].s[x] == q)

						tree[p].s[x] = nq, p = tree[p].fa;

				}

			}

			last = np;

		}

		int buf[N << 1];

		void radix_sort()

		{

			static int count[N];

			memset(count, 0, sizeof(int[len + 1]));

			for (int i = 1; i <= cnt; i++)

				++count[tree[i].max];

			for (int i = 1; i <= len; i++)

				count[i] += count[i - 1];

			for (int i = cnt; i > 0; i--)

				buf[count[tree[i].max]--] = i;

		}

		void build(const string &s)

		{

			init();

			len = s.size();

			for (int i = 0; i < s.size(); i++)

				insert(s[i]);

			radix_sort();

			for (int i = cnt; i > 0; i--)

				tree[tree[buf[i]].fa].size += tree[buf[i]].size;

		}

		inline ll query(const string &s)

		{

			static ll f[N << 1];

			static int num[N << 1];

			memset(f, 0, sizeof(ll[cnt + 1]));

			memset(num, 0, sizeof(int[cnt + 1]));

			ll ans = 0;

			int now = 1, len = 0;

			for (int i = 0; i < s.size(); i++)

			{

				int x = ctoi(s[i]);

				while (now && !tree[now].s[x])

					now = tree[now].fa, len = tree[now].max;

				if (now)

					now = tree[now].s[x], ++len;

				else

					now = 1, len = 0;

				f[now] += (len - tree[tree[now].fa].max), ++num[now];

			}

			radix_sort();

			for (int i = cnt; i > 0; i--)

			{

				int tmp = tree[buf[i]].fa;

				f[tmp] += (ll)num[buf[i]] * (tree[tmp].max - tree[tree[tmp].fa].max);

				num[tmp] += num[buf[i]];

			}

			for (int i = 2; i <= cnt; i++)

				ans += f[i] * tree[i].size;

			return ans;

		}

	}

	int work()

	{

		using namespace Auto_Suffix_Chicken;

		read(s1), read(s2);

		build(s1);

		write(query(s2));

		return (0^_^0);

	}

}

int main()

{

	return zyt::work();

}

巴特西

【BZOJ4566_洛谷3181】[HAOI2016]找相同字符（SAM）

题目：

分析：

代码：

最新文章

热门文章