分类 课程相关 下的文章

线段树模板

线段树模板,支持对区间做运算并求sum,基于POJ 3468
需要注意:

  • 数组开4倍大
  • 因为区间操作较频繁故打标记
  • 注意Update操作的位置
  • 均为1~n,所以包括左右,分段递归注意端点要被包含

- 阅读剩余部分 -

后缀数组

最长公共子串问题(LCS)

  • 定义:给定字符串长度最大的公有子串,使用后缀数组可达到$O(nLlogL)$,其中$n为字符串个数$,$L$为每个字符串长度
  • 等效于求两个后缀的公共前缀(LCP)

后缀数组相关概念

  • SA[i]:排名为i的后缀的位置(第i是谁)
  • Rank[i]:第i个后缀suffix(i)的排名
  • 对于已经排好序的字符串,任意两个的公共最长前缀为$LCP(s[i], s[j]) = min \{ LCP(s[k], s[k + 1]) , i \le k < j\}$,LCP转化成区间最小值RMQ问题
  • height[i]:定义height[i] = LCP(SA[i - 1], SA[i]),则$LCP(s[i], s[j]) = min \{ height[k] , i \le k < j\}$

- 阅读剩余部分 -

图与基本的图算法

图的基本概念及表示

图的基本概念

逻辑结构二元组B=(K,R),任意一对结点间都允许一个关系存在

  • 分类:无向图、有向图、带权图、稠密图、完全图、连通图等
  • 最一般的数据结构

表示:G=(V, E),有向完全图 $n * (n - 1)$ 条边,无向完全图 $n * (n - 1) / 2$ 条边

带权的连通图称为网络

图G有$n$个顶点,$e$条边,顶点$v_{i}$的度数为$TD(v_{i})$,则有$$e = \frac{1}{2} \sum_{i = 0}^{n - 1}TD(v_{i})$$

环:回路,无向图平行边不构成环,有向图两条边可构成环

- 阅读剩余部分 -

字符串匹配的相关算法

设文本串T与模式串P,分别长nm,字符串匹配即为找到所有的有效偏移,使PT中以该偏移出现

后缀重叠定理

假设x, y和z,x, y是z的后缀,如果|x|<|y|,那x是y的后缀;若相等,则x = y.

暴力匹配(brute force)算法

通过循环的方法,对共计n - m + 1个可能的s值进行检测,成功则返回位置,时间复杂度为$O((n - m + 1) m)$

NaiveStringMatcher(T, P)
n = T.length
m = P.length
for s = 0 to (n - m)
    if P[1..m] == T[s + 1..s + m]
        return true
int BruteForce(char* T, char* p)
{
    int tLen = strlen(t);
    int pLen = strlen(p);
  
    int i = 0;
    int j = 0;
    while (i < tLen && j < pLen)
    {
        if (t[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {   
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == pLen)
        return i - j;
    else
        return -1;
}

- 阅读剩余部分 -

Web技术概论

Arbitrary Definition of TCP/IP

Basic Web Protocol Suite

  1. Scheme:
    identify particular sources of information that server hosts
  2. The way browser present information
    the content itself contains the formatting information(raw information)
    HTML(Hypertext Markup Language) enables information creators to describe the format of the information to be rendered at browser side
  3. How to interpret the text stream ?
    server is responsible to look at the file name extension and map it to something called MIME(Multipurpose Internet Mail Extensions)
  4. How should a browser ask a server to deliver some information ?
    HTTP request browser tell the server more in addition to the file name
    HTTP response server tell the browser something like content type and when the file was last modified
  5. CGI(common gateway interface)
    allow a browser (user at browser side) to invoke some procedure at the server side, passing data to the procedure and getting processed result back, not just asking for pre-stored information







- 阅读剩余部分 -

最新文章

最近回复

分类

归档

其它

微博

基佬们

Fork me on GitHub