标签:LCS

HIHOCODER-WEEK122 最长公共子串

HIHOCODER-WEEK122 最长公共子串

本来看到两个最长公共子串,我就直接掏\(O({n^2})\)算法了……比如这个……

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace HIHOCODER_WEEK122
{
    class Program
    {
        static void Main(string[] args)
        {
            string str1 = Console.ReadLine();
            string str2 = Console.ReadLine();
            LCS lcs = new LCS(str1, str2);
            Console.WriteLine(lcs.Length);
        }
    }
    class LCS
    {
        public int Length { get; private set; }
        public LCS(string str1,string str2)
        {
            Length = 0;
            int lStr1 = str1.Length;
            int lStr2 = str2.Length;
            if (lStr1 == 0 || lStr2 == 0)
            {
                Length = 0;
                return;
            }
            int[,] table = new int[lStr1, lStr2];
            int longest = 0;
            for (int i = 0; i < lStr2; ++i)
                table[0, i] = (str1[0] == str2[i] ? 1 : 0);
            for (int i = 1; i < lStr1; ++i)
            {
                table[i, 0] = (str1[i] == str2[0] ? 1 : 0);

                for (int j = 1; j < lStr2; ++j)
                {
                    if (str1[i] == str2[j])
                    {
                        table[i, j] = table[i - 1, j - 1] + 1;
                    }
                }
            }
            for (int i = 0; i < lStr1; ++i)
            {
                for (int j = 0; j < lStr2; ++j)
                {
                    if (longest < table[i, j])
                    {
                        longest = table[i, j];
                    }
                }
            }
            Length = longest;
        }
    }
}

然后我就TLE了……
我想不对啊,然后一看……
要用后缀数组……
求完height之后判断一下,SA[i]和SA[i-1]是不是分别在两个串里。

//code source:http://www.xuebuyuan.com/2116000.html
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 420000;
int s[maxn], rs[maxn], sa[maxn], t[maxn], t2[maxn], c[maxn], Rank[maxn], height[maxn];
int n, m, k, tt, l1, l2;
char s1[maxn], s2[maxn];
#define min(x,y) x>y?y:x
#define max(x,y) x<y?y:x
inline int idx(char s)
{
	return s - 'a' + 2;
}
void getheight(int n)
{
	int i, k = 0;
	for (i = 0; i <= n; i++) Rank[sa[i]] = i;
	for (i = 0; i < n; i++)
	{
		if (k) k--;
		int j = sa[Rank[i] - 1];
		while (s[i + k] == s[j + k]) k++;
		height[Rank[i]] = k;
	}
}
void build_ss(int m, int n)
{
	n++;
	int i, *x = t, *y = t2;
	for (int i = 0; i < m; i++) c[i] = 0;
	for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
	for (int i = 1; i < m; i++) c[i] += c[i - 1];
	for (int i = n - 1; i >= 0; i--)
		sa[--c[x[i]]] = i;
	for (int k = 1; k <= n; k <<= 1)
	{
		int p = 0;
		for (i = n - k; i < n; i++) y[p++] = i;
		for (i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;

		for (i = 0; i < m; i++) c[i] = 0;
		for (i = 0; i < n; i++) c[x[y[i]]]++;
		for (i = 1; i < m; i++) c[i] += c[i - 1];
		for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
		swap(x, y);
		p = 1;
		x[sa[0]] = 0;
		for (i = 1; i < n; i++)
			x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p - 1 : p++;
		if (p >= n) break;
		m = p;
	}
}
bool diff(int x, int y)
{
	int a = min(x, y);
	int b = max(x, y);
	if (a<l1 && b>l1) return true;
	return false;
}
int main()
{
	cin >> s1;
	cin >> s2;
	l1 = strlen(s1);
	l2 = strlen(s2);
	for (int i = 0; i < l1; i++)
		s[i] = idx(s1[i]);
	s[l1] = 0;
	n = l1 + 1;
	for (int i = 0; i < l2; i++)
	{
		s[n++] = idx(s2[i]);
	}
	s[n] = 1;
	build_ss(128, n);
	getheight(n);
	int ans = 0;
	for (int i = 2; i < n; i++)
	{
		if (diff(sa[i], sa[i - 1]))
			ans = max(ans, height[i]);
	}
	cout << ans;
	return 0;
}