精华内容
下载资源
问答
  •  给出两个字符串串长度为m,长度为n字符串中如果有*字符,则代表当前位置可以匹配任何字符  求出个字符串在第字串中出现次数,及出现的位置开头在第个字符串的位置(从小到大输出...

    【传送门:BZOJ4259&BZOJ4503


    简要题意:

      给出两个字符串,第一个串长度为m,第二个串长度为n,字符串中如果有*字符,则代表当前位置可以匹配任何字符

      求出第一个字符串在第二个字串中出现的次数,及出现的位置开头在第二个字符串的位置(从小到大输出)


    题解:

      FFT,通配符匹配

      两道题几乎没区别

      对于两个串长度为i,它们的相似程度为$\sum_{j=0}^{i-1}(A[j]-B[j])^2$(A[j]!='*'&&B[j]!='*')

      把*设为0,则得到$\sum_{j=0}^{i-1}(A[j]-B[j])^2A[j]B[j]$

      显然只有当$\sum_{j=0}^{i-1}(A[j]-B[j])^2A[j]B[j]$为0时,A串和B串才能完全匹配

      那么对于这道题而言,设f(i)为以B的i位置为结尾的长度为n的子串与A串的相似程度

      先将n--,m--(方便写公式),然后在A后面补0

      显然$f(i)=\sum_{j=0}^{m}(A[j]-B[i-m+j])^2A[j]B[i-m+j]$

      我们把A数组翻转,就会得到$f(i)=\sum_{j=0}^{i}(A[j]-B[i-j])^2A[j]B[i-j]$

      然后把这个式子拆开就得到$f(i)=\sum_{j=0}^{i}A[j]^3B[i-j]-2*\sum_{j=0}^{i}A[j]^2B[i-j]^2+\sum_{j=0}^{i}A[j]*B[i-j]^3$

      皆大欢喜,直接三次FFT分别求就可以了


    参考代码(一):

    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    typedef long long LL;
    const double PI=acos(-1.0);
    struct Complex
    {
        double r,i;
        Complex(){}
        Complex(double _r,double _i){r=_r;i=_i;}
        friend Complex operator + (const Complex &x,const Complex &y){return Complex(x.r+y.r,x.i+y.i);}
        friend Complex operator - (const Complex &x,const Complex &y){return Complex(x.r-y.r,x.i-y.i);}
        friend Complex operator * (const Complex &x,const Complex &y){return Complex(x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r);}
    }a[1300000],b[1300000];
    int R[1300000];
    void fft(Complex *y,int len,int on)
    {
        for(int i=0;i<len;i++) if(i<R[i]) swap(y[i],y[R[i]]);
        for(int i=1;i<len;i<<=1)
        {
            Complex wn(cos(PI/i),sin(on*PI/i));
            for(int j=0;j<len;j+=(i<<1))
            {
                Complex w(1,0);
                for(int k=0;k<i;k++,w=w*wn)
                {
                    Complex u=y[j+k];
                    Complex v=w*y[j+k+i];
                    y[j+k]=u+v;
                    y[j+k+i]=u-v;
                }
            }
        }
        if(on==-1) for(int i=0;i<=len;i++) y[i].r/=len;
    }
    void calc(int n,int m)
    {
        int L=0;m+=n;
        for(n=1;n<=m;n<<=1) L++;
        memset(R,0,sizeof(R));
        for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|(i&1)<<(L-1);
        fft(a,n,1);fft(b,n,1);
        for(int i=0;i<=n;i++) a[i]=a[i]*b[i];
        fft(a,n,-1);
    }
    char s1[310000],s2[310000];
    int A[310000],B[310000];
    int q[310000];
    double f[310000];
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);n--;m--;
        scanf("%s%s",s1,s2);
        for(int i=0;i<=n;i++)
        {
            if(s1[n-i]=='*') A[i]=0;
            else A[i]=s1[n-i]-'a'+1;
        }
        for(int i=0;i<=m;i++)
        {
            if(s2[i]=='*') B[i]=0;
            else B[i]=s2[i]-'a'+1;
        }
        memset(f,0,sizeof(f));
        for(int i=0;i<=n;i++) a[i].r=A[i]*A[i]*A[i];
        for(int i=0;i<=m;i++) b[i].r=B[i];
        calc(n,m);
        for(int i=0;i<=m;i++) f[i]+=a[i].r;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i<=n;i++) a[i].r=A[i]*A[i];
        for(int i=0;i<=m;i++) b[i].r=B[i]*B[i];
        calc(n,m);
        for(int i=0;i<=m;i++) f[i]-=2.0*a[i].r;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i<=n;i++) a[i].r=A[i];
        for(int i=0;i<=m;i++) b[i].r=B[i]*B[i]*B[i];
        calc(n,m);
        for(int i=0;i<=m;i++) f[i]+=a[i].r;
        int cnt=0;
        for(int i=n;i<=m;i++) if(f[i]<0.5) q[++cnt]=i-n;
        printf("%d\n",cnt);
        if(cnt>0)
        {
            for(int i=1;i<cnt;i++) printf("%d ",q[i]+1);
            printf("%d\n",q[cnt]+1);
        }
        return 0;
    }

     


    参考代码(二):

    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    typedef long long LL;
    const double PI=acos(-1.0);
    struct Complex
    {
        double r,i;
        Complex(){}
        Complex(double _r,double _i){r=_r;i=_i;}
        friend Complex operator + (const Complex &x,const Complex &y){return Complex(x.r+y.r,x.i+y.i);}
        friend Complex operator - (const Complex &x,const Complex &y){return Complex(x.r-y.r,x.i-y.i);}
        friend Complex operator * (const Complex &x,const Complex &y){return Complex(x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r);}
    }a[1300000],b[1300000];
    int R[1300000];
    void fft(Complex *y,int len,int on)
    {
        for(int i=0;i<len;i++) if(i<R[i]) swap(y[i],y[R[i]]);
        for(int i=1;i<len;i<<=1)
        {
            Complex wn(cos(PI/i),sin(on*PI/i));
            for(int j=0;j<len;j+=(i<<1))
            {
                Complex w(1,0);
                for(int k=0;k<i;k++,w=w*wn)
                {
                    Complex u=y[j+k];
                    Complex v=w*y[j+k+i];
                    y[j+k]=u+v;
                    y[j+k+i]=u-v;
                }
            }
        }
        if(on==-1) for(int i=0;i<=len;i++) y[i].r/=len;
    }
    void calc(int n,int m)
    {
        int L=0;m+=n;
        for(n=1;n<=m;n<<=1) L++;
        memset(R,0,sizeof(R));
        for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|(i&1)<<(L-1);
        fft(a,n,1);fft(b,n,1);
        for(int i=0;i<=n;i++) a[i]=a[i]*b[i];
        fft(a,n,-1);
    }
    char s1[310000],s2[310000];
    int A[310000],B[310000];
    int q[310000];
    double f[310000];
    int main()
    {
        int m,n;
        scanf("%s%s",s1,s2);
        m=strlen(s1);n=strlen(s2);
        m--;n--;
        for(int i=0;i<=m;i++) B[i]=s1[i]-'a'+1;
        for(int i=0;i<=n;i++)
        {
            if(s2[n-i]=='?') A[i]=0;
            else A[i]=s2[n-i]-'a'+1;
        }
        memset(f,0,sizeof(f));
        for(int i=0;i<=n;i++) a[i].r=A[i]*A[i]*A[i];
        for(int i=0;i<=m;i++) b[i].r=B[i];
        calc(n,m);
        for(int i=0;i<=m;i++) f[i]+=a[i].r;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i<=n;i++) a[i].r=A[i]*A[i];
        for(int i=0;i<=m;i++) b[i].r=B[i]*B[i];
        calc(n,m);
        for(int i=0;i<=m;i++) f[i]-=2.0*a[i].r;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0;i<=n;i++) a[i].r=A[i];
        for(int i=0;i<=m;i++) b[i].r=B[i]*B[i]*B[i];
        calc(n,m);
        for(int i=0;i<=m;i++) f[i]+=a[i].r;
        int cnt=0;
        for(int i=n;i<=m;i++) if(f[i]<0.5) q[++cnt]=i-n;
        printf("%d\n",cnt);
        if(cnt>0) for(int i=1;i<=cnt;i++) printf("%d\n",q[i]);
        return 0;
    }

     

    转载于:https://www.cnblogs.com/Never-mind/p/8983886.html

    展开全文
  • 字符串S的长度为n,考虑i...n-1这后缀中符合条件的子串:首先需要记录两组数据,一组数据是从i向右找到的最长不含重复字符的子串长度prefixlen[i],二组数据是在i...n-1后缀中符合条件的子串之起始和结束...

    题目:求字符串最长不含重复字符的子串长度,如abcbec,就返回3.

    分析:

    利用动态规划(DP)原理,设字符串S的长度为n,考虑i...n-1这个后缀中符合条件的子串:首先需要记录两组数据,第一组数据是从i向右找到的最长不含重复字符的子串长度prefixlen[i],第二组数据是在i...n-1后缀中符合条件的子串之起始和结束位置,分别用 maxlenstart[i]和maxlenend[i]表示,注意二组数据满足:maxlenstart[i]-maxlenend[i]+1>=prefixlen[i],即从S[i]开始最左边的最长不含重复字符的子串长度与区间i...n-1中符合条件的子串长度可能相等;如果S[i]给prefixlen[i+1]增加一个字符长度,说明S[i]与右边长度为 prefixlen[i+1]个字符都不相同,这时需要分两种情况考虑,1)如果maxlenstart[i+1]==i+1即S[i+1...n-1] 中得到的最优子串的左边一个字符与S[i]也相邻,说明最大子串长度也应该增加1, 即设置maxlenstart[i]=i;注意此时如果prefixlen[i]总长度未在prefixlen[i+1]的基础上加1,说明第二组数据的长度不会比第一组数据长度大了,这是因为根据DP的计算过程,只要第二组数据与S[i]相邻,那么两组数据长度保证了前一步中是相等的;2)如果第二组数据不与S[i]相邻,则需要比较二组数据的长度了。

    具体实现时需要注意边界条件,设置prefixlen[n] = 0; maxlenstart[n] = n; maxlenend[n] = n-1;。

    代码:

    /**
     * 
     * @author ljs
     * 2011-07-09
     *
     */
    public class LongestSubseqWithUniqueChars {
    
    	public static int solve(String str){
    		int n = str.length();
    		int[] prefixlen=new int[n+1];
    		prefixlen[n] = 0;
    		int[] maxlenstart = new int[n+1];
    		maxlenstart[n] = n;
    		int[] maxlenend = new int[n+1];
    		maxlenend[n] = n-1;
    		
    		for(int i=n-1;i>=0;i--){
    			char c = str.charAt(i);
    			//caculate prefixlen[i] by prefixlen[i+1]
    			int j=0,k;
    			for(j=0,k=i+1;j<prefixlen[i+1];j++,k++){
    				if(c == str.charAt(k)){					
    					break;
    				}
    			}
    			prefixlen[i] = j+1;
    			
    			//caculate maxlenstart[i] and maxlenend[i]
    			maxlenstart[i] = maxlenstart[i+1];
    			maxlenend[i] = maxlenend[i+1];
    			if(maxlenstart[i+1] == i+1){
    				if(prefixlen[i] == prefixlen[i+1] + 1){
    					maxlenstart[i] = i;
    				}
    			}else{
    				//update the max len for i...n-1
    				if(maxlenend[i] - maxlenstart[i] + 1 < prefixlen[i]){
    					maxlenstart[i] = i;
    					maxlenend[i] = i + prefixlen[i] - 1;
    				}
    			}			
    		}
    		return maxlenend[0] - maxlenstart[0] + 1;
    	}
    	public static void main(String[] args) {
    		String str = "abcbec";
    		int maxlen = LongestSubseqWithUniqueChars.solve(str);
    		System.out.format("max len of substring with unique chars for string \"%s\" = %d.%n",
    				str,maxlen);
    		
    		str = "adabcbec";
    		maxlen = LongestSubseqWithUniqueChars.solve(str);
    		System.out.format("max len of substring with unique chars for string \"%s\" = %d.%n",
    				str,maxlen);
    		
    		str = "abadadabbc";
    		maxlen = LongestSubseqWithUniqueChars.solve(str);
    		System.out.format("max len of substring with unique chars for string \"%s\" = %d.%n",
    				str,maxlen);
    		
    		str = "ffdeefghff";
    		maxlen = LongestSubseqWithUniqueChars.solve(str);
    		System.out.format("max len of substring with unique chars for string \"%s\" = %d.%n",
    				str,maxlen);
    		
    		str = "abcbecghijkl";
    		maxlen = LongestSubseqWithUniqueChars.solve(str);
    		System.out.format("max len of substring with unique chars for string \"%s\" = %d.%n",
    				str,maxlen);
    		
    	}
    
    }
    

     

    测试输出:

    max len of substring with unique chars for string "abcbec" = 3.
    max len of substring with unique chars for string "adabcbec" = 4.
    max len of substring with unique chars for string "abadadabbc" = 3.
    max len of substring with unique chars for string "ffdeefghff" = 4.
    max len of substring with unique chars for string "abcbecghijkl" = 9.

    转载于:https://www.cnblogs.com/xulb597/archive/2012/05/23/2514483.html

    展开全文
  • 数组记录下A每个位置作为起点所能和B达到最大重合,最后判断查找数组中最大值,此时目标子字符串的起点下标(i)和 i 对应的长度(counter[i])都有了。 这是针对不知道字符串大小并且不占用额外空间做法,需要...
  • 四章 数组和字符串

    2019-12-01 23:56:09
    一、字符串 串:零或多字符组成的有限序列。 串长度:串中所包含的字符个数。 空串:长度为0的串,记为:" "。 非空串通常记为: S=" s1 ... 子串的位置:子串的第字符主串中的序号。 串的存储结构: ...

    一、字符串

    串:零个或多个字符组成的有限序列。 串长度:串中所包含的字符个数。 空串:长度为0的串,记为:" "。

    非空串通常记为: S=" s1 s2 …… sn " 其中:S是串名,双引号是定界符,双引号引起来的部分是串值 ,si(1≤i≤n)是一个任意字符。

    子串:串中任意个连续的字符组成的子序列。 主串:包含子串的串。 子串的位置:子串的第一个字符在主串中的序号。

    串的存储结构:

    (一)顺序串:用数组来存储串中的字符序列。

    1.表示串的长度的三种方法:

    方案1:用一个变量来表示串的实际长度。

    方案2:在串尾存储一个不会在串中出现的特殊字符作为串的终结符,表示串的结尾。

    方案3:用数组的0号单元存放串的长度,从1号单元开始存放串值。

    (二)链接串:用链接存储结构来存储串

    二、模式匹配:

     给定主串S="s1s2…sn"和模式T="t1t2…tm", 在S中寻找T 的过程称为模式匹配。

    如果匹配成功,返回T 在S中的位置,如果匹配失败,返回-1。

    (假设串采用顺序存储结构,串值从0号单元开始存放。)

    1.模式匹配——BF(Brute-Force)算法

    基本思想: 从主串S的第0个字符开始和模式T 的第0个字符进行比较,     若相等,则继续比较两者的后续字符;     否则,从主串S的第1个字符开始和模式T 的第0个字符进行比较,     重复上述过程,直到T 中的字符全部比较完毕,则说明本趟匹配成功;或S中字符全部比较完,则说明匹配失败。

    说明:模式匹配过程要进行多趟的匹配,每趟匹配要进行若干次的比较。

    伪代码:

    1. 在串S和串T中设比较的起始下标i和j;

    2. 循环直到S或T的所有字符均比较完;    

    2.1 如果S[i]==T[j],继续比较S和T的下一个字符;    

    2.2 否则,将i和j回溯(i=i-j+1,j=0),准备下一趟比较;

    3. 如果T中所有字符均比较完,则匹配成功,返回匹配的起始比较下标(i-j);否则,匹配失败,返回-1;

    int BF(char S[ ], char T[ ])
    {
         i=0; j=0;   
        while (i<S.Length()&&j<T.length())
        {
             if (S[i]==T[j]) {
                 i++;   j++;
             }  
             else {
                 i=i-j+1;    j=0;
             }   
         }
         if (j>=T.length())  return (i-j);   
         else return -1;
    }
    

    设串S长度为n,串T长度为m,在匹配成功的情况下,考虑两种极端情况:

    ⑴ 最好情况:不成功的匹配都发生在串T的第一个字符。

    在i-1趟不成功的匹配中共比较了i-1次, 第i趟成功的匹配共比较了m次, 所以总共比较了i-1+m次.所有匹配成功的可能情况共有n-m+1种。

    (2)最坏情况:不成功的匹配都发生在串T的最后一个字符。

    设匹配成功发生在si处,则在这次成功的比较过程中共进行了多少次比较?(包括之前失败的比较) 在i-1趟不成功的匹配中比较了(i-1)×m次, 第i趟成功的匹配共比较了m次, 所以总共比较了i×m次。

    所有匹配成功的可能情况共有n-m+1种。

    BF性能低的原因:在每趟匹配不成功时存在大量回溯,没有利用已经部分匹配的结果。

    2.模式匹配——KMP(Knuth-Morris-Pratt)算法

     i可以不回溯,模式向右滑动到的新比较起点k ,并且k 仅与模式串T有关!

    三、多维数组

    将线性表中的元素进行扩充——>多维数组。

    (多维)数组——线性表中的数据元素可以是线性表,但所有元素的类型相同。

    广义表——线性表中的数据元素可以是线性表,且元素的类型可以不相同。

    (一)、

    1.数组:数组是由一组类型相同的数据元素构成的有序集合,每个元素受n(n≥1)个线性关系的约束,并称该数组为 n 维数组。

    (1)数组的特点:元素本身可以具有某种结构,属于同一数据类型; 数组是一个具有固定格式和数量的数据集合。

    二维数组是数据元素为线性表的线性表

    (2)数组的基本操作:

    a.存取:给定一组下标,读出对应的数组元素;

    b.修改:给定一组下标,存储或修改与其相对应的数组元素。

    存取和修改操作本质上只对应一种操作——寻址

    (3)存储方式

    数组没有插入和删除操作,所以,不用预留空间,适合采用顺序存储。

    数组的存储结构与寻址——二维数组:

    常用的映射方法有两种:

    按行优先:先行后列,先存储行号较小的元素,行号相同者先存储列号较小的元素。

    按列优先:先列后行,先存储列号较小的元素,列号相同者先存储行号较小的元素。

    四、矩阵的压缩存储

    特殊矩阵和稀疏矩阵:

    特殊矩阵:矩阵中很多值相同的元素并且它们的分布有一定的规律。 稀疏矩阵:矩阵中有很多零元素。

    压缩存储的基本思想是: ⑴ 为多个值相同的元素只分配一个存储空间; ⑵ 对零元素不分配存储空间。

    1.特殊矩阵的压缩存储——对称矩阵  :对称矩阵的特点:对称矩阵特点:aij=aji

    2.特殊矩阵的压缩存储——三角矩阵

    (1)下三角矩阵的压缩存储:

    存储下三角元素、对角线上方的常数只存一个。

    (2)上三角矩阵的压缩存储:

    存储上三角元素、对角线下方的常数只存一个。

    3.特殊矩阵的压缩存储——对角矩阵 (带状矩阵)

    对角矩阵:所有非零元素都集中在以主对角线为中心的带状区域中,除了主对角线和它的上下方若干条对角线的元素外,所有其他元素都为零。

    4.十字链表结点类的定义

    template<class T>
    class OLNode
    {
    	
    public:
    	int row,col;
    	T element;
    	OLNode<T>* right,*down;
    public:
    	OLNode(){right=NULL;down=NULL;};
    };
    

    五、广义表

       广义表(列表):  n (  0 )个表元素组成的有限序列,记作: LS = (a0, a1, a2, …, an-1)     LS是表名,ai是表元素,它可以是表 (称为子表),可以是数据元素(称为原子)。   n为表的长度。n = 0 的广义表为空表。

    长度:广义表LS中的直接元素的个数; 深度:广义表LS中括号的最大嵌套层数。 表头:广义表LS非空时,称第一个元素为LS的表头; 表尾:广义表LS中除表头外其余元素组成的广义表。

    广义表与线性表的区别:

    线性表的成分都是结构上不可分的单元素;广义表的成分可以是单元素,也可以是有结构的表;线性表是一种特殊的广义表;广义表不一定是线性表,也不一定是线性结构。

    广义表的基本运算:

    (1)求表头GetHead(L):非空广义表的第一个元素,可以是一个单元素,也可以是一个子表

    (2)求表尾GetTail(L):非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表

    广义表的存储结构——头尾表示法

    定义结点结构:

    enum Elemtag {Atom, List}; 
    
    template <class T>
    struct GLNode {  
       Elemtag tag; 
       union    {
          T data; 
          struct 
          {
              GLNode *hp, *tp; 
           } ptr;                            
        };
    };
    

    广义表的特点:

    1)有次序性:一个直接前驱和一个直接后继

    有长度:=表中元素个数

    有深度:=表中括号的重数

    可递归:自己可以作为自己的子表

    可共享:可以为其他广义表所共享

     

     

     

     

     

     

     

     

    展开全文
  • 字符串

    2019-12-01 13:05:23
    字符串 一、串的逻辑结构 串:零或多字符组成的有限序列。 串长度:串中所包含的字符个数。 空串:长度为0的串,记为:" “。...子串的位置:子串的第字符主串中的序号。 顺序串:用...

    字符串
    一、串的逻辑结构
    串:零个或多个字符组成的有限序列。
    串长度:串中所包含的字符个数。
    空串:长度为0的串,记为:" “。
    非空串通常记为:
    S=” s1 s2 …… sn "
    其中:S是串名,双引号是定界符,双引号引起来的部分是串值 ,si(1≤i≤n)是一个任意字符。
    子串:串中任意个连续的字符组成的子序列。
    主串:包含子串的串。
    子串的位置:子串的第一个字符在主串中的序号。
    顺序串:用数组来存储串中的字符序列
    如何表示串的长度?
    方案1:用一个变量来表示串的实际长度。
    方案2:在串尾存储一个不会在串中出现的特殊字符作为串的终结符,表示串的结尾。
    方案3:用数组的0号单元存放串的长度,从1号单元开始存放串值。
    二、模式匹配
    给定主串S="s1s2…sn"和模式T=“t1t2…tm”,
    在S中寻找T 的过程称为模式匹配。
    BF算法
    基本思想:
    从主串S的第0个字符开始和模式T 的第0个字符进行比较,
    若相等,则继续比较两者的后续字符;
    否则,从主串S的第1个字符开始和模式T 的第0个字符进行比较,
    重复上述过程,直到T 中的字符全部比较完毕,则说明本趟匹配成功;或S中字符全部比较完,则说明匹配失败。
    说明:模式匹配过程要进行多趟的匹配,每趟匹配要进行若干次的比较
    算法描述:

    1. 在串S和串T中设比较的起始下标i和j;

    2. 循环直到S或T的所有字符均比较完;
      2.1 如果S[i]==T[j],继续比较S和T的下一个字符;
      2.2 否则,将i和j回溯(i=i-j+1,j=0),准备下一趟比较;

    3. 如果T中所有字符均比较完,则匹配成功,返回匹配的起始比较下标(i-j);否则,匹配失败,返回-1;
      int BF(char S[ ], char T[ ])
      {
      i=0; j=0;
      while (i<S.Length()&&j<T.length())
      {
      if (S[i]==T[j]) {
      i++; j++;
      }
      else {
      i=i-j+1; j=0;
      }
      }

      if (j>=T.length()) return (i-j);

      else return -1;

    }

    设串S长度为n,串T长度为m,在匹配成功的情况下,考虑两种极端情况:

    ⑴ 最好:不成功的匹配都发生在串T的第一个字符。

    例如:S=“aaaaaaaaaabcdccccc”

            T="bcd "
    

    最坏情况:不成功的匹配都发生在串T的最后一个字符。

    例如:S=“aaaaaaaaaaabccccc”

            T="aaab" 
    

    在每趟匹配不成功时存在大量回溯,没有利用已经部分匹配的结果。

    主串不回溯,模式就需要向右滑动一段距离。(i不移动,j>=0的位置继续进行下一次的比较)

    KMP算法

    i可以不回溯,模式向右滑动到的新比较起点k ,并且k 仅与模式串T有关!

    令k = next[ j ],则:

    next[j]表征着模式T中最大相同前缀子串和左子串(真子串)的长度。

    next[j]的算法分析:

    k=next[j-1](由next[]的 定义可以知道:t0t1…tk-1= tj-k…tj-3tj-2)

    1. 如果t[k]t[j-1]或k-1(不存在长度相同的前缀子串和左子串 )

      则t0t1…tk-1tk= tj-k…tj-3tj-2tj-1,因此

      next[j]=k+1,next[j]计算结束

    否则, 查找t0t1…tk的最长左子串

       k=next[k],转 1 继续执行
    

    void Compute_Next(char t[], int next[])

    {

    int j,k;
    
      next[0]=-1;j=1;
    
    while(t[j]!='\0')
    
    {
    
       k=next[j-1];
    
       while((k!=-1)&&(t[k]!=t[j-1]))
    
           k=next[k];
    
       next[j]=++k;
    
       j++;
    
    }
    

    }

    1.在串S和串T中分别设比较的起始下标i和j;

    1. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕

      2.1 如果S[i]==T[j],继续比较S和T的下一个字符;否则

      2.2 将j向右滑动到next[j]位置,即j=next[j];

      2.3 如果j=-1,则将i和j分别加1,准备下一趟比较;

    2. 如果T中所有字符均比较完毕,则返回匹配的起始下标;否则返回-1;

    int KMP_FindPat(char *s, char *t,int *next){

    int i=0,j=0,k;
    
    while(s[i]!='\0' && t[j]!='\0') {
    
       if(j==-1 || s[i]==t[j])  {
    
                 i++;
    
                 j++;
    
           }
    
       else
    

    j=next[j];

    }
    
    if(t[j]=='\0')
    
       return i-j;
    
    else
    
       return -1;
    

    }

    展开全文
  • 字符串: 串的逻辑结构: 串:零或多字符组成的有限序列。 串长度:串中所包含的字符个数。 空串:长度为0的串,记为:" “。 ...子串的位置:子串的第字符主串中的序号。 串的存储结...
  • 重复的子字符串 给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。...也就是说,s长度为 n’ 的前缀就是 s’,并且这之后的每一个位置上的字符 s[i],都需要与它之前的第 n’个字
  • 字符串 1.串:零或多字符组成的有限序列。 2.串长度:串中所包含的字符个数。 3.空串:长度为0的串,记为:" " 4.非空串通常记为: S=" s1 s2 …… sn " ...8.子串的位置:子串的第字符主串中的序号。 9....
  • 字符串和多维数组 字符串 (1)串的逻辑结构 串:零或多字符组成的有限序列。 串长度:串中所包含的字符个数。...空串:长度为0的串,记为:" “。...子串的位置:子串的第字符主串中...
  • 这里我读入的是一个长度为9的字符串,显然字符数组c是不会越界的,更不会改变x的值。 程序没有任何问题,但程序运行完输出的x竟然是0,如果把程序的c[10]调到c[11]也就和程序输出的结果...
  • 最少翻转使得字符串没有连续三相同字符问题定义解法一解法二 ...以下假设给定的字符串长度为N,使用动态规划,对某位置 i,该位置的字符情况有四种: 它是连续的x 它是连续的x 它是一...
  • P4173 残缺的字符串 fft

    2018-07-27 19:33:00
    假设上面的串s,s长度为m,下面的串是p,p长度为n,先考虑没有*情况那么\(\sum_{j=1}^m(s_{i+j}-p_j)^2=0\)就表示能够从i开始匹配,现在考虑有*情况,我们只需要让有*和任意字符匹配即可,那么把公式变成\(\sum_{j=...
  • 八次-字符串(一)

    2019-11-11 23:39:25
    字符串和多维数组 字符串 (1)串的逻辑结构 串:零或多字符组成的有限序列。 串长度:串中所包含的字符个数。 空串:长度为0的串,记为:" “。 非空串通常记为: ...子串的位置:子串的第字符主串中...
  • 文件压缩【字符串

    2020-05-11 20:03:29
    该算法具体如下:对一个长度为n的字符串S,首先根据它构造n个字符串,其中第i个字符串由将S的前i-1个字符置于末尾得到。然后把这n个字符串按照首字符从小到大排序,如果两个字符串的首字符相等,则按照它们S中的...
  • 1.字符串 串:零或多字符组成的有限序列。 串长度:串中所包含的字符个数。 空串:长度为0的串,记为:" "。 ...非空串通常记为: ... S=" s1 s2 …… sn " ...子串的位置:子串的第字符主串中的序...
  • 字符串哈希(模板)

    2019-08-12 15:46:49
    寻找长度为n的串S中的匹配串T(长度为m)出现的位置或次数属于字符串匹配问题。 字符串哈希就是将每字符串转化为一数值,然后遍历主串,判断主串起始位置i长度为m的字符串的哈希值与匹配串的哈希值是否...
  • 数组、字符串

    2019-12-01 18:50:43
    字符串 串的逻辑结构 串:零或多字符组成的有限序列。 串长度:串中所包含的字符个数。 空串:长度为0的串,记为:" "。 非空串通常记为: ...子串的位置:子串的第字符主串中的序号。 串的存储...
  • // 返回字串t串spos个字符之后的位置,若不存在,则返回-1 // 其中,t非空,1 <= pos <= s.size() int Index(const char *s,const char *t, int pos){  i = pos;  j = 1;  while (s...
  • 一、字符串 1、字符串的定义 串:零或多字符组成的有限序列。 串长度:串中所包含的字符个数。 空串:长度为0的串,记为:" "。...非空串通常记为: S=" s1 s2 …… sn " ...子串的位置:子串的第字符主串中
  • 数组与字符串

    2019-12-01 14:14:18
    的逻辑结构 :零或多字符组成的有限序列。 长度:中所包含的字符个数。 空串:长度为0的,记为:" “。 非空串通常记为: S=” s1 s2 …… sn " ...子串的位置:子串的第字符中的序号。 S1=...
  • 代码目的:找到字符串s中,最长唯一回文字符串。 我写代码能dev c++中运行并找到正确结果,可是提交到leetcode中,显示runtime error,并显示“bb”无法识别。dev c++中测试可以识别。 另外用vs2012编译运行...
  • 字符串和多维数组

    2019-10-25 20:37:22
    字符串(串):零或多字符组成的有限序列 串长度:串中所包含的字符个数 空串:长度为0的串,记为:" " ...子串的位置:子串的第字符主串中的序号。 串的存储结构 : 字符串是数...
  • 给你一字符串 s 和一 长度相同 整数数组 indices 。...法一:原地排序,时间复杂度O(n),思路是遍历字符串s,每遍历到一字符,查找该字符应该在的位置,之后交换该字符和它应该在的位置的
  • 在串s的第i个位置插入串s1形成串s2----------------\n"); printf("----------------f.从串s的第i个字符开始连续删除j个字符形成串s3---------------\n"); printf("----------------g.将串s的第i个字符开始的j个...
  • 三行输入整数M,表示字符串S的长度四行输入字符串S。 输出格式 共一行,输出所有出现位置的起始下标(下标从0开始计数),整数之间用空格隔开。 数据范围 1≤N≤105 1≤M≤106 说明: next[i]=j :p串的 p...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 186
精华内容 74
关键字:

在长度为n的字符串s的第i个位置