恍惚间，九月都已经快过完了，原本炙烤大地的太阳也收敛了。
本该在生日那天写点什么，却发现自己已经失去了思考的力量。
思考。
曾经的我热爱思考，遇到什么事情都会想想为什么，怎么办。
现在的我，却总喜欢按部就班，按着固定的模式完成一切。
这令我感到惶恐，惴惴不安。
这辈子都不想做别人的傀儡，却总像猫一样，被提线架上的晃动的绳子所吸引。
这样不行。
这份工作很好，能有很多时间思考。
这份工作也不好，磨平了我思考的动力。
围城一般。
也许是时候考虑，什么时候离开这里。
我更愿意去北极烤面包。
（来自动画《四月是你的谎言》）
1、读100本人文社科、政治哲学、历史等方面的书或小说
2、学习一些心理学知识，学会如何安慰人，学会控制欲望
3、写大量代码
4、学习写作
5、参加一次大的竞赛，比如数学建模大赛等
6、确定正式工作，有稳定收入
7、学会以正确的方式尊重人，学会如何处理亲密关系和个人空间之间的联系
8、减少玩游戏、瞎混的时间
9、学英语，至少到IELTS 6.5水平
10、继续练习萨克斯
11、尽量减肥到75KG，保持一定的运动和节食
备考……希望能拿到奖学金
本来看到两个最长公共子串，我就直接掏\(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;
}
hello world!