发表于 | 分类于

题目连接：

https://vjudge.net/problem/SPOJ-LCS

Description

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is simple, for two given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Input

The input contains exactly two lines, each line consists of no more than 250000 lowercase letters, representing a string.

Output

The length of the longest common substring. If such string doesn’t exist, print “0” instead.

Sample Input

alsdfkjfjkdsal
fdjskalajfkdsla

Sample Output

3

Hint

题意

求两个串的最长公共子串长度

题解：

对a串建后缀自动机，b串在建好的自动机上跑，跑的过程和建树是一样的，如果Next[p][c]存在则nowlen++，否则p回退到fa[p]直到Next[p][c]存在，并更新nowlen为len[p]+1,对整个过程的nowlen取max就是答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int mx = 1e6+5;

struct SAM_automaton {
    int Next[mx][26], len[mx], fa[mx];
    int last, tot;
    int newnode() {
        tot++;
        for (int i = 0; i < 26; i++) Next[tot][i] = 0;
        return tot;
    }

    void init() {
        tot = 0;
        last = newnode();
    }

    void add(int c) {
        int p = last;
        int np = last = newnode();
        len[np] = len[p] + 1;
        while (p && !Next[p][c]) {
            Next[p][c] = np;
            p = fa[p];
        }
        if (!p) fa[np] = 1;
        else {
            int q = Next[p][c];
            if (len[q] == len[p] + 1) fa[np] = q;
            else {
                int nq = newnode();
                len[nq] = len[p] + 1;
                fa[nq] = fa[q];
                for (int i = 0; i < 26; i++) Next[nq][i] = Next[q][i];
                fa[q] = fa[np] = nq;
                while (p && Next[p][c] == q) {
                    Next[p][c] = nq;
                    p = fa[p];
                }
            }
        }
    }
}SAM;

char a[mx], b[mx], str[mx];

int main() {
    SAM.init();
    
    scanf("%s%s", a, b);
    int lena = strlen(a);
    int lenb = strlen(b);
    for (int i = 0; i < lena; i++) SAM.add(a[i]-'a');
    int ans = 0, len = 0;
    for (int i = 0, p = 1; i < lenb; i++) {
        int c = b[i] - 'a';
        if (SAM.Next[p][c]) {
            len++;
            p = SAM.Next[p][c];
        } else {
            while (p && !SAM.Next[p][c]) p = SAM.fa[p];
            if (!p) {
                p = 1;
                len =0;
            } else {
                len = SAM.len[p] + 1;
                p = SAM.Next[p][c];
            }
        }
        ans = max(ans, len);
    }

    printf("%d\n", ans);    
    return 0;
}

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;
const int mx = 1e5+5;
typedef long long ll;

bool vis[mx];
int sum[mx], prim[mx], mu[mx], cnt = 0;

void get_mu(){
    mu[1] = 1;
    for(int i = 2; i< mx; i++){
        if(!vis[i]) {
            prim[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && prim[j]*i < mx; j++) {
            vis[prim[j]*i] = 1;
            if(i % prim[j] == 0) break;
            else mu[i*prim[j]] = -mu[i];
        }
    }
    sum[0] = 0;
    for (int i = 0; i < mx; i++) sum[i] = sum[i-1]+ mu[i];
}


int main() {
    get_mu();
    int n, m;
    scanf("%d%d", &n, &m);

    int len = min(n, m);
    int last;

    ll ans = 0;
    /*利用n/i连续区间数值相同的性质进行分块计算，可把复杂度降为sqrt(n) */
    for (int i = 1; i <= len; i=last+1) {
        last = min(n/(n/i), m/(m/i));
        ans += 1LL * (sum[last] - sum[i-1]) * (n/i) * (m/i);
    }
    printf("%lld\n", ans);

}

发表于 | 分类于

通配符

通配符 作用
？ 匹配一个任意字符，
* 匹配0个或任意多个字符，也就是匹配任意内容
[] 匹配括号中任意一个字符。
[-] 匹配括号中任意一个字符。-代表一个范围例如[a-z]，表示匹配一个小写字母
[^] 逻辑非，表示匹配不是括号内的任意一个字符，例如[^0-9]，表示匹配一个不是数字的字符

Bash中其它特殊符号

符号 作用
‘ ‘ 单引号。单引号中所有的特殊符号，如“$”和“`”（反引号）都没有特殊含义。
“ “ 双引号。在双引号中特殊符号都没有特殊含义，但是“$”、“`”和“\”是个例外，拥有“调用变量的值”、“引用命令”和转义的特殊含义。
` ` 反引号。反引号括起来的内容是系统命令，在Bash中会先执行它。和$()作用一样，不过推荐使用$()，因为反引号非常容易看错
$() 和反引号作用一样，用来引用系统命令。
# 在Shell脚本中，#开头的行代表注释。
$ 用于调用变量的值，如需要调用变量name时，需要用$name的方式得到变量的值

\

 转义符,跟在\之后的特殊符号将失去特殊含义，变为普通字符。如\$将输出“$”符号，而不是当做变量引用

发表于 | 分类于

标准输入输出

设备 设备文件名 文件描述符 类型
键盘 /dev/stdin 0 标准输入
显示器 /dev/stdout 1 标准输出
显示器 /dev/stderr 2 标准错误输出

输出重定向

类型 符号 作用
标准输出重定向 命令>文件 以覆盖方式把命令的正确输出输出到指定的文件中
标准输出重定向 命令>>文件 以追加方式把命令的正确输出输出到指定的文件中
标准错误输出重定向 错误命令>文件 以覆盖方式把命令的错误输出输出到指定的文件中
标准错误输出重定向 错误命令>>文件 以追加方式把命令的错误输出输出到指定的文件中 
1
2
3
4
5
6
7
8
9
10
11
12
[bpdwn@localhost ~]$ touch right.out
[bpdwn@localhost ~]$ touch error.out
[bpdwn@localhost ~]$ ls > right.out 
[bpdwn@localhost ~]$ cat right.out 
data.txt
error.out
hello.sh
right.out
test.cpp
[bpdwn@localhost ~]$ lst 2> error.out 
[bpdwn@localhost ~]$ cat error.out 
-bash: lst: 未找到命令
  • 2与>(>>)之间不能有空格

正确输出和错误输出同时保存

命令 作用
命令 > 文件 2>&1 以覆盖方式把正确输出和错误输出都保存到同一文件当中
命令 >> 文件 2>&1 以追加方式把正确输出和错误输出都保存到同一文件当中
命令 &> 文件 2>&1 以覆盖方式把正确输出和错误输出都保存到同一文件当中
命令 &>> 文件 2>&1 以追加方式把正确输出和错误输出都保存到同一文件当中
命令>>文件1 2>>文件2 把正确的输出追加到文件1中，把错误的输出到文件2中

输出重定向

命令 作用
命令<文件 把文件作为命令的输入
命令<<文件 把两个符号直接的内容作为命令的输入 
1
2
3
4
wc [选项][文件名]
-c 统计字节数
-w 统计单词数
-l 统计行数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[bpdwn@localhost ~]$ cat test.txt 
hello
 world
apple

[bpdwn@localhost ~]$ wc < test.txt 
 4  3 20
[bpdwn@localhost ~]$ 
/*输出行 单词数 字符数*/

[bpdwn@localhost ~]$ wc << hello
> world
> apple
> orange
> hello
 3  3 19
[bpdwn@localhost ~]$ 
/*统计两个hello之间的字符*/