位置:首页 » 技术 » LCP poj 2217 寻觅最长公共子串

LCP poj 2217 寻觅最长公共子串

日期:2014-03-31 阅读:0num
Advertisement

LCP poj 2217 寻找最长公共子串

题目:http://poj.org/problem?id=2217

首先解释,DP中的最长公共子序列和此处的最长公共子串区别-------------------序列可以是不连续的,但是子串是连续的

其次,LCP,lcp[i]就是lcp[rank[i]]和lcp[rank[i]+1]的最长公共前缀,那么把两个字符串接起来,然后找最长的lcp,就是答案

思路还是比较清晰的

上代码:

/*******************************************************/
//poj 2217 lcp+sa by Pilgrim
//最长公共子串---注意与动态规划的最长公共子序列不同
//2014.4.2
/******************************************************/

#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>

#define MAXN 10010
#define INF 0x80000000
//0x7fffffff
//0x80000000

using namespace std;

int n,k;//n=strlen(s);

int Rank[MAXN];
int tmp[MAXN];

/*使用Rank对sa排序*/
bool cmpSa(int i, int j)
{
    if(Rank[i] != Rank[j])return Rank[i] < Rank[j];
    else
    {   /*下面的Rank[t],已经是以t开头长度小于等于k/2的,
        sa[i]的名次,只是以i开头的后缀,而长度不同*/
        int ri = i+k <=n? Rank[i+k]:-1;
        int rj = j+k <= n ? Rank[j+k]:-1;
        return ri <rj;
    }
}

/*计算SA*/
void con_sa(char *s, int *sa)
{
    /*n=strlen(s);  必要时注明*/
    /*初始化sa和rank保证两点
        1、Rank[i]表示下标为i的是第几大,必须表示出相对大小,可以直接用字符代表其大小
        2、sa[1...n]值为1..n*/
    for(int i=0;i<=n;i++){
        sa[i]=i;Rank[i] = i < n?s[i]:-1;
    }

    /*利用长度为k的字符串对长度为2*k的字符串排序*/
    for(k=1;k<=n;k*=2)/*注意此代码中k是全局变量 别乱用,循环必须从1开始,因为0*2=0*/
    {
        sort(sa,sa+n+1,cmpSa);
        tmp[sa[0]] = 0; /*此时tmp只是暂存rank*/
        for(int i=1;i<=n;i++){
            tmp[sa[i]] = tmp[sa[i-1]] +(cmpSa(sa[i-1],sa[i])?1:0);
            /*这一句很关键,等号右侧的sa[i]在此循环里表示第i大的长度小于等于k/2的字符串,
              从而求出第i大的长度小于等于k的字符串的sa[i]*/
        }
        for(int i=0;i<=n;i++){
            Rank[i] = tmp[i];
        }
    }
}

void construct_lcp(char *s,int *sa,int *lcp)
{
    //n=strlen(s);
    for(int i=0; i<=n; i++)Rank[sa[i]]=i;

    int h=0;
    lcp[0]=0;
    for(int i=0;i<n;i++)
    {
        int j=sa[Rank[i]-1];

        if(h>0)h--;
        for(; j+h<n && i+h<n; h++)
        {
            if(s[j+h]!=s[i+h])break;
        }
        lcp[Rank[i]-1]=h;
    }
}

int main()
{
    int sa[MAXN],lcp[MAXN];
    char s[MAXN],t[MAXN];
    char c;
    int ncase,mmax,len,leng;

    while(scanf("%d",&ncase)!=EOF)
    {
        while(ncase--)
        {
            mmax =0;
            while((c=getchar())==' '|| c=='\n');
            s[0]=c;
            int tt=1;
            while((c=getchar()) != '\n')
            {
                s[tt++]=c;

            }

            s[tt]='\0';
            while((c=getchar())==' '|| c=='\n');
            t[0]=c;
            tt=1;
            while((c=getchar()) != '\n')
            {
                 t[tt++]=c;

            }
            t[tt]='\0';
            len=strlen(s);
            leng =len+1+strlen(t);
            strcpy(s+len+1,t);
///////////////////////////////////////////////
//for(int i=0;i<leng;i++)
 //   putchar(s[i]);
//putchar('\n');
            n=leng;
            con_sa(s,sa);
            construct_lcp(s,sa,lcp);

           for(int i=0;i<leng;i++)
            {
              if((sa[i]<len) != (sa[i+1]<len))
                  mmax=max(mmax,lcp[i]);
            }
            printf("Nejdelsi spolecny retezec ma delku %d.\n",mmax);
        }
    }

    return 0;
}

LCP poj 2217 寻觅最长公共子串的相关内容

相关文章
  • LCP poj 2217 寻觅最长公共子串

    LCP poj 2217 寻找最长公共子串 题目:http://poj.org/problem?id=2217 首先解释,DP中的最长公共子序列和此处的最长公共子串区别-------------------序列可以是不连续的,但是子串是连续的 其次,LCP,lcp[i]就是lcp[rank[i]]和lcp[rank[i]+1]的最长公共前缀,那么把两个字符串接起来,然后找最长的lcp,就是答案 思路还是比较清晰的 上代码: /***********************************

  • poj 1226 hdu 1238 Substrings 求若干字符串正串及反串的最长公共子串 2002亚洲赛天津市预选题

    poj 1226 hdu 1238 Substrings 求若干字符串正串及反串的最长公共子串 2002亚洲赛天津预选题 题目:http://poj.org/problem?id=1226 http://acm.hdu.edu.cn/showproblem.php?pid=1238 其实用hash+lcp可能也可以,甚至可能写起来更快,不过我没试,我最近在练习后缀数组,所以来练手 后缀数组的典型用法之一----------------后缀数组+lcp+二分 思路:1.首先将所有的字符串每读取一个

  • POJ 标题2774 Long Long Message(后缀数组,求最长公共子串长度)

    POJ 题目2774 Long Long Message(后缀数组,求最长公共子串长度) Long Long Message Time Limit: 4000MS Memory Limit: 131072K Total Submissions: 23696 Accepted: 9705 Case Time Limit: 1000MS Description The little cat is majoring in physics in the capital of Byterland. A p

  • 后缀数组之最长公共子串 poj 2774

    用后缀数组求两个串的最长公共子串的长度 详见罗穗骞的论文 [cpp] #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cstdlib> #define MAXN 1000005 using namespace std; int r[MAXN]; int wa[MAXN],

  • POJ 2774 最长公共子串

    题意: 给定2个字符串,求最长公共子串的长度 思路: 把两个字符串相连得到S,则他们的公共子串就是部分S的后缀子串的前缀. 因为是相同的子串,所以sa必然是相邻的,因此扫一下height,若sa[i] 与 sa[i-1] 的后缀分别在分割符$前后,那就是两个字符串的后缀,求其最长公共前缀(即height[i])就是一个公共子串. #include #include #include #include #include #include using namespace std; #define r

  • POJ 2774 后缀数组:求最长公共子串

    思路:其实很简单,就是两个字符串连接起来,中间用个特殊字符隔开,然后用后缀数组求最长公共前缀,然后不同在两个串中,并且最长的就是最长公共子串了. 注意的是:用第一个字符串来判断是不是在同一个字符中,刚开始用了第二个字符的长度来判断WA了2发才发现. #include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #defi

  • POJ3294-Life Forms 后缀数组+2分答案 大于k个字符串的最长公共子串

    POJ3294--Life Forms 后缀数组+二分答案 大于k个字符串的最长公共子串 Life Forms Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 10800 Accepted: 2967 Description You may have wondered why most extraterrestrial life forms resemble humans, differing by superficial t

  • 最长公共子串

    最长公共子串(Longest Common Substring)是一个非常经典的问题,它的基本描述为"给定两个字符串,求出它们之间最长的相同子字符串(要求连续)的长度".例如以下两个字符串S和T的的最长公共子串"howmuchiloveyoumydearmother",长度为27. S="yeshowmuchiloveyoumydearmotherreallyicannotbelieveit" T="yeaphowmuchiloveyo

  • poj-3450 KMP求多个字符串的最长公共子串

    poj--3450 KMP求多个字符串的最长公共子串 思路与前面的3080一样 代码如下: #include<iostream> #include<cstdio> #include<cstring> using namespace std; char str1[220],str2[220]; int next[220],n; char ch[4400][220]; void GetNext() { int j=0; int len=strlen(str2+1); nex

  • 求最长公共子串 递归写的

    求助 求最长公共子串 递归写的 程序运行不过 帮我看看哪里错误了 基本思想还是以前的求解方法:对于字符串a,b,尽量用b的最大的子字符串c去匹配另外一个字符串a,如果c不是a的子串,那么用字符串b的长度比b少1的子串去匹配a,直到匹配到了为止或者子串的长度为0. #include<stdio.h> #include<stdlib.h> #include<iostream> #include<string.h> using namespace std; int

  • 求两个字符串的最长公共子串 (字母务须相邻)

    求两个字符串的最长公共子串 (字母必须相邻) 上一篇<求最长公共子串(可以不相邻)>的另一种变换题目,这个相对于上一篇,稍稍简单,不过这个算法的时间复杂度不太好,更简单的算法,有时间我再整理下. 问题:求最长公共子串,字符必须相邻. 代码: public class common { public static void findCommon(String s1, String s2) { int i;//第一个游标从0 ~ length-1游走 int j;//第二个游标从i+1 ~ len

  • 求两个字符串的最长公共子串(字母可以不紧邻,但是顺序不变)

    求两个字符串的最长公共子串(字母可以不相邻,但是顺序不变) 不知道为什么笔试总是遇到这些题目,看来经典算法,大家都喜欢啊,这个是LCS问题,动态规划. 问题:求两个字符串的最长公共子串,字母可以不相邻,但是顺序不变 代码: public class lcs { public static void LCS_Print(String str1, String str2) { int length1 = str1.length(); int length2 = str2.length(); int

  • 应用倍增法后缀数组以及RMQ求解N个字符串最长公共子串有关问题

    应用倍增法后缀数组以及RMQ求解N个字符串最长公共子串问题 /** * @see IOI2009国家集训队论文<后缀数组--处理字符串的有力工具> * @author leon * */ public class SuffixArray { int max_char = '\uffff'; char separator = '$'; char eof = '#'; int[][] rmq; String text = ""; int min_len = Integer.MA

  • 从优化到再优化,最长公共子串

    概览 最长公共子串问题的基本表述为: 给定两个字符串,求出它们之间最长的相同子字符串的长度. 最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同,然后取得相同最长的那个.对于一个长度为n的字符串,它有n(n+1)/2 个非空子串.所以假如两个字符串的长度同为n,通过比较各个子串其算法复杂度大致为O(n4).这还没有考虑字符串比较所需的时间.简单想想其实并不需要取出所有的子串,而只要考虑每个子串的开始位置就可以,这样可以把复杂度减到O(n3). 但这个问题最好的解决办法是动态规划

  • 软件工程师面试题精选100题(20)-最长公共子串

    程序员面试题精选100题(20)-最长公共子串 这个题目待研究... 题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串. 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串. 分析:求最长公共子串(Longest Co

  • SPOJ1811最长公共子串有关问题(后缀自动机)

    SPOJ1811最长公共子串问题(后缀自动机) 题目:http://www.spoj.com/problems/LCS/ 题意:给两个串A和B,求这两个串的最长公共子串. 分析:其实本题用后缀数组的DC3已经能很好的解决,这里我们来说说利用后缀自动机如何实现. 对于串A和B,我们先构造出串A的后缀自动机,那么然后用B串去匹配,对于B,我们一位一位地扫描,维护一个ans值,表示从 B串的开始到B[i]的这个子串与A的最长公共子串. 假设现在到B[i-1]的最长公共子串长度为ans,然后我们来看B[

  • 找工作常识储备(2)-数组字符串那些经典算法:最大子序列和,最长递增子序列,最长公共子串,最长公共子序列,字符串编辑距离,最长不重复子串,最长回文子串 找工作常识储备(2)-数组字符串那些经典算法:最大子序列和,最长递增子序列,最长公共子串,最长公共子序列,字符串编辑距离,最长不重复子串,最长回文子串

    找工作知识储备(2)---数组字符串那些经典算法:最大子序列和,最长递增子序列,最长公共子串,最长公共子序列,字符串编辑距离,最长不重复子串,最长回文子串 作者:寒小阳 时间:2013年9月. 出处:http://blog.csdn.net/han_xiaoyang/article/details/11969497. 声明:版权所有,转载请注明出处,谢谢. 0.前言 这一部分的内容原本是打算在之后的字符串或者数组专题里面写的,但看着目前火热进行的各家互联网公司笔试面试中,出现了其中的一两个内容,

  • 动态规划求解最长公共子串中的有关问题

    动态规划求解最长公共子串中的问题 今天学习了动态规划的相关思想,随后找了一些经典的题目希望能加深一下印象.然而在求解"最长公共子串"的问题时却发现了一些问题. 一般来说,在求解这类问题的时候,大都依据以下原理: 定义lcs[i][j]为序列"a0,a1,-,ai-2"和"b0,b1,-,bj-1"的最长公共子序列的长度,计算lcs[i] [j]可递归地表述如下: (1)lcs[i][j] = 0 如果i=0或j=0: (2)lcs[i][j] =

  • 【CodeCraft赛事】Problem 7——X-man(最长公共子串LCS变种) 【CodeCraft赛事】Problem 7——X-man(最长公共子串LCS变种)

    [CodeCraft比赛]Problem 7--X-man(最长公共子串LCS变种) 题目:点击打开链接 Question 7 Problem Statement Dr. Charles Xavier is trying to check the correlation between the DNA samples of Magneto and Wolverine. Both the DNAs are of length N, and can be described by using all

  • 【华为OJ】【081-查找两个字符串a,b中的最长公共子串】

    题目描述 查找两个字符串a,b中的最长公共子串 输入描述 输入两个字符串 输出描述 返回重复出现的字符 输入例子 abcdefghijklmnop abcsafjklmnopqrstuvw 输出例子 jklmnop 算法实现 import java.util.Scanner; /** * Author: 王俊超 * Date: 2016-01-04 08:43 * Declaration: All Rights Reserved !!! */ public class Main { public

最新文章
  • 求推荐Mac上最接近甚至超过Fiddler的软件

    求推荐Mac上最接近甚至超过Fiddler的软件. 我试用过Charles,意外情况不少,抓包失败率不低. --cut-- ohsc在2012-04-15 19:03:4回答到: Charles挺好用的 xinyu198736在2012-04-15 19:05:3回答到: charles 但是有时候抓不到chrome的包,不知道为什么.而且貌似查看header和response都不太方便.但是对相同host的分类做的挺方便 neildd在2012-04-15 19:21:3回答到: 我上次用过F

  • 白色短袖t恤怎么搭配更好看 白色短袖t恤怎么搭配更好看

    白色T恤是最常见最普通的夏季百搭单品了,但不是人人都能穿出它的生命力来!爱美网服饰小编推荐夏日时尚白色T恤,教你白色T恤美搭术,夏日就要清爽,白色T恤绝对少不了! 领口处有三角形镂空设计的短袖T 清凉感十足,领口处包边处理做工精致,浅色系会有点透,袖口卷边固定. 面料简洁清爽 配色尽显高端质感,雪纺和合成皮质地的拼接设计,合成皮的部分是加工成相当于雪纺厚度的那种面料. 简约白色圆领T恤,衣身上有简约的线条点缀设计,百搭舒适,休闲大方,搭配红色短裙束腰穿时尚又舒适. 领边三角镂空的设计独具个性,宽

  • 今天 V2EX 在做一些网络层面的调整

    刚才看到 @jedyu 的这个帖子 http://www.v2ex.com/t/116577 反馈说今天无法在杭州电信的网络上打开 www.v2ex.com ,但是 v2ex.com 正常. 如果在不用代理的情况下,你无法访问 www.v2ex.com 的话,请告知我一下你 ping www.v2ex.com 得到的 IP. 谢谢大家. --cut-- kqz901002在2014-06-09 17:46:0回答到: 现在ping值只有30ms,lbr.ogslb.com 感觉快多了 kqz90

  • 凉拌小菜的做法

    通常是凉拌黄瓜或者儿菜 黄瓜切条,去掉老的子粒(内瓤),用刀将黄瓜拍拍,切丁,码盐. 儿菜切片(丝),码盐: 蒜,剁成茸,葱,切葱花,然后装一碗里,撒上一些黑芝麻. 烧热菜油(菜油比色拉油.调和油香),淋进装有蒜茸.葱花.芝麻的碗里:然后,放醋.糖.味精合匀. 滤去码好盐的黄瓜丁(儿菜)里出的水,将小碗里合好的调料到进黄瓜丁(儿菜)里拌匀,装盘后还可根据口味,勾上一点辣椒红油.

  • Photoshop设计华丽的汽车壁纸 Photoshop设计华丽的汽车壁纸

    来源:思缘论坛 作者:等你转身 本教程介绍汽车壁纸的制作方法.虽然用到的元素不多,不过做在配色和设计上下了很多功夫.颜色选择的经典的紫色和蓝色,非常华丽.再加上一些光感背景,感觉非常时尚.不过制作的过程介绍的不是很详细,需要根据提示,慢慢去发挥. 最终效果 1.新建一个1024 * 768像素的文档,如下图. 2.把背景层解锁,再设置图层样式,选择渐变叠加,参数设置如下图. 3.选择菜单:图层 > 拼合图层,再转为普通层,然后执行:滤镜 > 模糊 > 动感模糊,参数设置如下图. 4.用矩

  • 孚日变卖旗下光伏资产 “家纺大王”多元化战略折戟

    当企业把一个产业规模做到极致后,是应该继续坚守,还是多元发展?这是困扰许多中国企业家的难题. 近日,全球最大家纺企业--孚日股份因连年亏损.盈利无望而变卖旗下所有光伏资产.昔日的"毛巾大王"用6年的时间.以8亿投资为代价,给这一问题提供了新的注脚. 困境下的转型 "目前,公司的光伏生产线和相关资产已有多个买家表达出收购意向,但最终尚未确定出售的对象和价格."全球最大家纺企业--孚日股份董秘张萌说道,公司投资的光伏产业常年亏损.盈利无望,忍痛砍掉也是无奈之举. 俗话说

  • 中式风格的手绘电视背景墙效果图 中式风格的手绘电视背景墙效果图

    一般来说,人们在进行手绘电视背景墙时,一般会选择卡通.风景.植物等方面的图案,但是有些人钟情于中式风格,下面就给大家推荐一些中式风格手绘电视背景墙效果图. 手绘背景墙材质编辑 布面手绘:布面手绘材质有,亚麻布.棉麻混纺布.丝绸布等. pvc手绘:一般是绘制在壁纸厂制作好的素色壁纸上,材质为pvc由于表层做过处理,国画无法绘制多用丙烯颜料彩绘. 真丝手绘:丝绸材质表层有轻微的珍珠光泽,由于是天然真丝织物,质感较柔和比较适合室内装饰,色泽温润雅致,色调丰富. 金箔手绘:纯金打造是高端奢华产品,造价较

  • 大五码繁体字库(BIG5码)的安装使用方法

    大五码繁体字库(BIG5码)的安装使用方法 1.首先安装BIG5码字体,安装方法:打开"控制面版",找到"字体"打开,将需要的字体文件复制到字体文件夹中即可,安装完毕最好重新启动电脑.其它字体安装方法同上.(华康.金梅.超世纪等繁体字库都属于此类大五码字体,字体扩展名为TTF.或TTC). 2.在word里把需要的汉字输入工作区内,然后将文字全选,选择"工具"菜单中的"语言",内有"中文简繁转换"选择&qu

  • 整体厨房效果图 整体厨房效果图

    整体厨房也叫整体橱柜,是将厨房用具和厨房电器进行系统搭配而成的一个有机的整体形式.对于厨房来说,不仅需要讲究实用功能,也应该注重其外表,要能够上的厅堂.以下我们就来看看本站网的编辑为大家提供的整体厨房图片吧. 整体厨房图片一 整体厨房效果图设计合理非常的重要,按照自己的顺手的方式安装比较好,以免以后用的非常的不方便,上水管和下水管的安装要根据水槽的地方而定,所以整体厨房这些问题都很细致. 整体厨房图片二 整体厨房效果图设计非常的必要,整体厨房装修最重要的就是尺寸问题,所以一定要精确尺寸,如果量的

  • eclips: An error has occurred. see the log file解决办法

    eclips: An error has occurred. see the log file 昨天清理了下电脑结果今天开启eclipse的时候就悲剧了 log: !SESSION Fri May 18 17:13:45 CST 2012 ------------------------------------------ !ENTRY org.eclipse.equinox.launcher 4 0 2012-05-18 17:13:45.125 !MESSAGE Exception laun

热门推荐
  • 步步高高管微博自曝vivo X3真机局部照片 步步高高管微博自曝vivo X3真机局部照片 自vivo Xplay之后,步步高又打造了一款定位稍低,但音乐卖点更加鲜明的新机:vivo X3.根据之前的报道,其定位介于X1/X1S和XPlay之间,目前正在内测,有望在本月发布,售价目前尚未确定,预计不会超过2699元. 今天,步步高通信科技有限公司产品经理@vivo韩少在其个人微博首次曝光了vivo X3的真机局部照片,并表示X3的是毫不造假的5.XXmm机身,摄像头并不会凸出,影响视觉体验,而且会标配3.5mm耳机接口. 而且值得一提的是,此次曝光的型号为vivo X3t,支持TD-S
  • 火锅怎么吃健康呢 火锅怎么吃健康呢 冬季到了很多人喜欢吃火锅,冬季吃火锅却是人生一大快事,但火锅吃的不好容易吃出病来,火锅怎么吃健康?来谈谈吃火锅的注意事项: 本站阅读配图 1.火锅涮食一定要将食材煮熟 许多食客为了尝鲜,喜欢将肉片.生菜等稍微一涮就吃,这种吃法不可取. 为保证去除生鲜食品中残留有病原微生物和寄生虫的危害,因此一定要将食材煮熟食用. 食用火锅时切忌生食或食用没熟透的食料.一般来讲,薄肉片在沸腾的锅中烫1分钟左右,肉的颜色由鲜红色变为灰白才可以吃.刚从火锅中取出的鲜烫食物应放在碗内稍凉一下再吃,以免烫伤口腔.食道黏膜
  • 智能路由器有什么用 智能路由器有什么用 随着移动互联网的发展,现在智能家庭越来越接近大众了,也影响着很多传统的设备制造商,这里牵扯到一种关键的网络设备--智能路由器,关于智能路由器有什么用这个问题,很多消费者还不太了解.现在小米的智能路由器已经上市好一段时间了,小米是路由器行业的新进入者,是互联网公司,传统的路由器设备厂商确实要努力了,竞争者越来越多,也越来越激烈,智能路由器哪个好?看看各家的情况. 一.TP-Link 传统家用网络设备的行业领军者,据说早几年就出货量全球第一了,国内外都占据着最高的市场份额,现在具体的数据不是非常清楚
  • 身体这样时千万不能泡脚 身体这样时千万不能泡脚 身体这样时千万不能泡脚 1太饱太饿时都不宜泡脚 泡脚时,避免在过饱.过饥或进食状态下,因为沐足会加快全身血液循环,容易出现头晕不适的情况.饭后半小时内不宜泡脚,会影响胃部血液的供给. 2婴幼儿没必要泡脚 小孩是"纯阳之体",本身就容易发热,爱上火.如果再用较热的水泡脚.发汗,会热上加热.特别是婴幼儿,对温度的感觉和大人不一样,大人觉得水温稍热,对孩子来说已经是很烫了.但他们又不太会表达,所以很容易烫伤柔嫩的皮肤.从这个角度说,也不建议用热水泡脚.每天用温水把小脚好好洗洗就行,洗完后,可
  • 算法9-3:最大流跟最小切割的理论 算法9-3:最大流跟最小切割的理论 算法9-3:最大流和最小切割的理论 本章节介绍最大流问题和最小切割问题的关系.其实这两个问题是等价的. 现在把一个网络分成A和B两个部分,我们定义A到B的净流量交叉(Net flow across)就是从A到B的最大流量减去从B到A的最大流量. 接下来介绍流量值定理(Flow-value lemma).令f为网络中任何一个流,令(A,B)为网络的任何一种切割方法,那么(A,B)的净流量交叉就等同于f的流量值.下图展示了流量值定理. 通俗的解释一下吧.首先将网络切割两个部分A和B,那么AB之间的流
  • Chrome 调试老是进入 Paused in debugger状态 Chrome 调试老是进入 Paused in debugger状态 Chrome 调试总是进入 Paused in debugger状态 Chrome 调试总是进入 Paused in debugger状态 转 这两天用chrome调试的时候总是鼠标移动下就进入Paused in debugger状态,根本就没办法调试js.百思不得其解,各种设置都试过了.百度很n久,度娘不给力啊.最后google之,在Stackoverflow上找到了答案http://stackoverflow.com/questions/12833514/paused-in-debugger