分类:未分类

2019.9.22

2019.9.22

恍惚间,九月都已经快过完了,原本炙烤大地的太阳也收敛了。
本该在生日那天写点什么,却发现自己已经失去了思考的力量。
思考。
曾经的我热爱思考,遇到什么事情都会想想为什么,怎么办。
现在的我,却总喜欢按部就班,按着固定的模式完成一切。
这令我感到惶恐,惴惴不安。
这辈子都不想做别人的傀儡,却总像猫一样,被提线架上的晃动的绳子所吸引。
这样不行。
这份工作很好,能有很多时间思考。
这份工作也不好,磨平了我思考的动力。
围城一般。

也许是时候考虑,什么时候离开这里。
我更愿意去北极烤面包。

一点计划,和薰的笑容

一点计划,和薰的笑容


(来自动画《四月是你的谎言》)
1、读100本人文社科、政治哲学、历史等方面的书或小说
2、学习一些心理学知识,学会如何安慰人,学会控制欲望
3、写大量代码
4、学习写作
5、参加一次大的竞赛,比如数学建模大赛等
6、确定正式工作,有稳定收入
7、学会以正确的方式尊重人,学会如何处理亲密关系和个人空间之间的联系
8、减少玩游戏、瞎混的时间
9、学英语,至少到IELTS 6.5水平
10、继续练习萨克斯
11、尽量减肥到75KG,保持一定的运动和节食

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;
}