精华内容
下载资源
问答
  • 字符子串个数

    万次阅读 多人点赞 2017-06-21 20:58:54
    长度为n的字符 1、有n(n+1)/2 +1个子; 2、非空子:n(n+1)/2; 3、非空真子:n(n+1)/2– 1。


    长度为n的字符串

    1、有n(n+1)/2 +1个子串;

    2、非空子串:nn+1/2

    3、非空真子串:nn+1/2– 1

    展开全文
  • 给一字符,出它的一最长的回文子串.所谓回文子串,指的是一字符从左到右和从右到左遍历得到的序列是相同的.例如”abcba”是回文子串,而”abcab”就不是回文子串. 思考 如何确定一字符是回文?这是一...
  • 最大子串与最大子序列区别:最大子串指字符中连续公共子串,而最大子序列时,公共字符可以不连续(但字符前后顺序不能改变)。例如:"abcgftyk"与"abcgshykd",其最长公共子串为"abcg",而最长子序列为"abcgyk" ...

    最大子串与最大子序列区别:最大子串指字符串中连续公共子串,而求最大子序列时,公共字符可以不连续(但字符前后顺序不能改变)。例如:"abcgftyk"与"abcgshykd",其最长公共子串为"abcg",而最长子序列为"abcgyk"

    题目:查找两个字符串a,b中的最长公共子串。若有多个,输出在较短串中最先出现的那个。

    题目解析

    假设两个字符串分别是:str1=”bab”和str2=”caba”。可以采用二维数组a[][]来存储str1[i]与str2[j]的关系,如果二者相等,则a[i][i]为1,否则为0。矩阵如下图所示

                                                                                       

    可知当两字符串相同字符连续出现时,在矩阵中表现为a[i][j]=a[i-1][j-1]。则对角线值均为1且最长时,就为所求的最大公共子串。如"ba"/"ab"。由于题目不是求最大公共子串的长度,而是求最大公共子串(可知子串不唯一,所以要求输出先出现的那个,即"ba")

    然而问题来了,如何寻找最长的斜对角线呢?如果遍历整个矩阵的话,时间和空间复杂度无疑会增加,因此,当str1[i]==str2[j]时,令a[i][j]=a[i-1][j-1]+1。(i=0时,直接赋值为1)。如下图所示。

                                                                     image           

    可以进一步简化空间复杂度,我们每次求a[i][j]时,只与前一列相关,而我们可以边计算矩阵中元素值边记录最大长度,因此之前的可以抛弃。故而可以用一维数组 b[ ] 来保存,并且动态更新,计算第i列的时候,覆盖之前数组中保存的第i-1列的值。此时需要从j最大元素开始计算,即按红圈顺序从下往上更新,b[i]=b[i-1]+1(从上往下的话,b[i]会覆盖求b[i+1]时需要的前一列的b[i]值)

    具体程序如下:(C++)

    #include<cstring>
    #include<iostream>
    using namespace std;
    int maxlss(string str1,string str2)
    {
        if(str1.empty()||str2.empty())
            return 0;
        if(str1.size()>str2.size()) //交换两个数组,保证str1长度更短,便于后续求最短字符串中最先出 
                                    //现的最大子串
        {
            string tmp=str1;
            str1=str2;
            str2=tmp;
        }
        int m=str1.size(),n=str2.size();
        int *lcs=new int[n];  //一维数组,保存最长公共子串相关信息
        memset(lcs,0,sizeof(int)*n); //赋初值为0
        int ln=0,pos;//公共子串最大值ln,所求最先出现的最大公共子串最后一个元素在str1中的位置pos
        
        for(int i=0;i<m;i++)   //不断更新数组值并保存最大公共字串长度和位置信息,并输出
        {
            for(int j=n-1;j>=0;j--) 
            {
                if(str1[i]==str2[j])
                {
                    if(j==0)
                        lcs[j]=1;
                    else
                        lcs[j]=lcs[j-1]+1;
                }
                else
                    lcs[j]=0;
                if(lcs[j]>ln)
                {
                    ln=lcs[j];
                    pos=i;
                }
            }
        }
        cout<<str1.substr(pos-ln+1,ln)<<endl;
        return ln;
    }
    
    int main()
    {
        string a,b;
        while(cin>>a>>b)
        {
            maxlss(a,b);
        }
        return 0;
    }

    如果题目只是要求求解最大公共子串长度,则不需要交换str1和str2。

     

    展开全文
  • 问题描述: 一字符的非空子是指字符中长度至少为 1 的连续的一段字符组成的。...一整数,表示含有多少个子串。 样例输入: aaab 样例输出: 7 代码: public static void main(String[]

    问题描述:

    一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成的串。
    例如,字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab,一共 7 个。
    注意在计算时,只算本质不同的串的个数。
    请问,字符串0100110001010001 有多少个不同的非空子串?
    

    输入格式:

    长度至少为1的连续字符串。
    

    输出格式:

    一个整数,表示含有多少个子串。
    

    样例输入:

    aaab
    

    样例输出:

    7
    

    代码:

    public static void main(String[] args) throws Exception {
    
    		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    		String line = reader.readLine();
    		// 用list存储不同的子串
    		List<String> list = new ArrayList<String>();
    		for (int i = 0; i < line.length(); i++) {
    			for (int j = 0, k = i + 1; k <= line.length(); j++, k++) {
    				// 去掉重复的子串
    				if (list.contains(line.substring(j, k))) {
    					continue;
    				} else {
    					// 把无重复的子串加入到list中去
    					list.add(line.substring(j, k));
    				}
    			}
    		}
    		// 输出list的长度
    		System.out.println(list.size());
    	}
    

    展开全文
  • 取字符的最大子串

    千次阅读 2019-10-21 15:42:36
    子串定义:将给定的字符去除任意字符后,例如acb的子串有a、b、c、ab、ac、cb、acb。 子串大小:按照英文字母表的顺序进行排序,如acb的最大子串为cb。 代码如下: -- 取字符的最大子串 function ...

    子串定义:将给定的字符串去除任意个字符后,例如acb的子串有a、b、c、ab、ac、cb、acb。

    子串大小:按照英文字母表的顺序进行排序,如acb的最大子串为cb。

    代码如下:

    -- 求取字符串的最大子串
    function GetMaxSubString(str)
        -- body
        local str = string.reverse(str)
        local ret_str = ""
        local curMax = 0
        for k=1,#str do
            if string.byte(str, k) >= curMax then
                ret_str = ret_str .. string.sub(str, k, k)
                curMax = string.byte(str, k)
            end
        end
        ret_str = string.reverse(ret_str)
        print(str .. "的最大子串为:" .. ret_str)
        return ret_str
    end
    
    str = GetMaxSubString("dhfaad")
    print(str)

    运行结果:

    daafhd的最大子串为:hfd
    hfd

     

    展开全文
  • # -*- coding:'utf-8' -*- A = input("请输入长字符:") B = input("请输入子字符:") p = A.count(B) ... 计算子字符串个数 ''' length_a = len(a) length_b = len(b) count = 0 i = 0 for ...
  • 文章目录题目描述:代码实例: 题目描述: 返回顺序s中从第i(1《i《n...//字符12345一共5个数,为什么分配6空间,原因是c语言中字符后面自带一/0多以多分配一空间 int length; }SqString; //获取子串
  • 求解字符所包含子串的个数

    万次阅读 多人点赞 2018-03-01 10:38:58
    重要的事情说三遍)备注:空串属于子串2、中字符均不相同:n字符构成的字符,假设每字符都不一样,问有多少个子答案:n(n+1)/2+1友情提示:每字符均不相同解析:包含1字符的子串共n包含2字符的...
  • 【每一个子串必然是某个后缀的前缀】,因此我们统计出所有的后缀中有多少不同的前缀,就是所有不重复子串的数量了 而这相同的前缀个数,当然就是所有height之和啦。 所以答案就是n*(n-1)/2-∑height[i] ...
  • 题目链接 P2408 不同子串个数 后缀数组中的sa[i]记录了后缀排序为i的后缀,如果它和后缀排序中前一个子串的最长公共前缀是LCP,那么我们可以把它的总长减去他们的LCP就是答案了,而此时的LCP就是height[i]。 此处...
  • 给定一字符s,其中全部数字所代表的数字之和。 【要求】 忽略小数点字符,例如”A1.3″,其中包含两数字1和3。 如果紧贴数字子串的左侧出现字符’-’’,当连续出现的数量为奇数时,则数字视为负,连续...
  • nowcoder---统计子串个数(C语言)

    千次阅读 2020-11-18 22:01:06
    大家都知道China的英文缩写是CHN,那么给你一字符s,你需要做的是统计s中子“CHN”的个数。 子串的定义:存在任意下标a < b < c,那么“s[a]s[b]s[c]”就构成s的一个子串。如“ABC”的子串有“A”、“B...
  • 字符子串计算方法

    千次阅读 2019-08-24 10:31:24
    字符的任意片段都是子串: 对于字符不重复的长度为n的...字符“software”有8字符,可是设置间隔的位置有9,使用C(9,2)=36即可求得字符“software”的所有子串。因为空串也是子串,故还需要加上1,总共3...
  • int count_max_len(char str[]) { int count ; char *p = str; int max = 0; while(*p != '\0') { count = 0; while(*p >= '0' && *p <= '9') { count++;... if(count >...
  • 不同子串个数

    2019-10-05 17:29:13
    不同子串个数 时间限制1.00 s ...给你一长为N的字符不同的子串的个数 我们定义两个子串不同,当且仅当有这两个子串长度不一样 或者长度一样且有任意一位不一样。 子串的定义...
  • 字符子串的个数

    万次阅读 多人点赞 2019-06-25 21:57:13
    字串:中任意连续的字符组成的子序列称为该的字串。 空串属于字串 (1)长度为n的字符,如果中字符各不相同,则字串的个数为n(n+1)/2+1 解析: 包含1字符的子串共n ... 综上所述:子串个数共:1...
  • 寻找子串个数() 描述 从字符s中找出字符t出现的次数,没有则输出0 格式 输入格式 输入两字符 输出格式 输出个数 样例 样例输入 112121 121 样例输出 2 #include <stdio.h> #include <stdlib.h>...
  • 给定n数组,这n数组的最长公共子串的长度,例如: paths = [[0,1,2,3,4], [2,3,4], [4,0,1,2,3]] 的最长公共子串为[2,3],长度为2。 这类问题可以使用字符hash来解决,首先是二分最长公共子串的长度。对于...
  • dp[i]表示以i结尾的合法的括号序列个数 维护一栈,左括号push他的位置到栈中,右括号取出栈顶 dp[i] = dp[sta[top] - 1] + 1 然后对dp数组求和 int sta[MAXN * 10], top, ans[MAXN * 10]; ll Ans; char s[MAXN * ...
  • #include <bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 5; char s[N]; int ma[2020]; int main() { scanf("%s", s); ... int res = 0, t = 1, n = s...
  • 字符中的子串个数

    千次阅读 2018-02-18 11:59:15
    #include &lt;stdio.h&gt; #include &lt;string.h&gt; int find(char *str1,char *str2) { int i,j; int len1=strlen(str1),len2=strlen(str2); int count=0; for(i=0;... {...
  • C++ 字符的所有子串

    千次阅读 2019-09-04 17:27:37
    字符的所有子串的核心就是利用substr这函数,所以一定要搞懂这函数。第二变量是偏移量。 下面是源码: #include<iostream> #include<string> using namespace std; void ...
  • 字符的最大子串问题

    万次阅读 2018-09-03 16:04:48
    基于字符的最大子串问题是经常面试的问题,想要表现的好不但要会基础的方法,同时还要学会优化的算法。 ...一:字符的最大公共子串 #include&lt;iostream&gt; #...
  • 题目(字符的非空子数量) 一字符的非空子是指字符中长度至少为 1 的连续的一段字符组成 的。...//subString(i,j)是字符子串从下标 i 开始,到 j 结束。类似于指针移动。 简谈HashSet和TreeSet
  • 题目:求串text中所包括test中的最大子串。比方text="abcgfdd",test="hhmcgfp",则最大子串为cgf。长度为3 我的解法例如以下: 从大到小分别出text的子串。用kmp比較是否在text中,若在就是最大子串。返回...
  • 字符子串

    2019-03-10 17:02:44
    S=”UP!UP!...子串的公式 :(n * (n+1)) / 2 + 1,其中,n 为所字符的字符个数,不包括空格 子串的定义是:任意连续的字符组成的子序列(包括空串),不能有重复。 题目来源牛客网 ...
  • } //获取子串个数 public static int getSubStringNum(String str1,String str2) { String max=null,min=null; int count = 0; int index = 0; if(str1.length()==str2.length()) { if(str1....
  • 由于本身初识Python,很多Python知识并不了解,所以这里主要使用了回溯法其子字符,然后通过Python中列表的sort()方法将其按老师要求排序。 str1 = input("请输入一单词:") res = [] s1 = "" def outlist(s, ...
  • 本文实例讲述了C语言字符的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下:#include "stdio.h"#include "string.h"#include "stdlib.h"void getCommon(char str1[],char str2[],char * str3)...
  • 字符子串个数和最大子串长度。 (需要注意一下子和子序列概念并不相同) 字符1:str1,字符2:str2 用dp[i][j]表示以str1[i]和str[j]结尾的相同子串的长度。 则转移方程显然为: 1.str1[i] != ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 135,285
精华内容 54,114
关键字:

串的子串个数怎么求