精华内容
下载资源
问答
  • 问题描述 给定一大串 A 和一模式串 B,求 B 在 A 的...第三行一正整数 m,表示串 B 的长度。 第四行包含一长度为 m 的串 B。 保证串 A,B 只包含小写字母。 输出格式 对于每 B 在 A 中出现的位置,...

    问题描述

    给定一个大串 A 和一个模式串 B,求 B 在 A 的哪些位置出现(输出这些出现位置的起始位置,下标从 0 开始)。

    输入格式

    第一行一个正整数 n,表示串 A 的长度。

    第二行包含一个长度为 n 的串 A。

    第三行一个正整数 m,表示串 B 的长度。

    第四行包含一个长度为 m 的串 B。

    保证串 A,B 只包含小写字母。

    输出格式

    对于每个 B 在 A 中出现的位置,输出单独一行一个整数表示该次出现的起始位置。

    对于所有的这些位置,请升序(从小到大)输出。

    样例输入

    7
    abcabca
    4
    abca
    

    样例输出

    0
    3

    提示

    [此题是单模匹配算法的练习题。]

    [可以尝试暴力匹配、KMP算法、Boyer-Moore算法、Rabin-Karp算法,并比较它们的效果。]

     

    一. 伪代码

    二. 具体实现

    #include <bits/stdc++.h>
    using namespace std;
    // ================= 代码实现开始 =================
    vector<int> Next;
    // 这是匹配函数,将所有匹配位置求出并返回
    // n:串 A 的长度
    // A:题目描述中的串 A
    // m:串 B 的长度
    // B:题目描述中的串 B
    // 返回值:一个 vector<int>,从小到大依次存放各匹配位置

    vector<int> match(int n, string A, int m, string B) {
       Next.resize(m);
       int j = Next[0]= -1;
       for(int i =1; i<m; ++i){
            while( j >= 0 &&B[i] != B[j+1])
                j = Next[j];
            if(B[i] == B[j+1])
                ++j;
            Next[i] = j;
       }
       j = -1;
       vector<int> ans;
       for(int i=0; i<n; ++i){
            while(j >=0 &&A[i] != B[j+1])
                j = Next[j];
            if(A[i] == B[j+1])
                ++j;
            if(j == m-1)
                ans.push_back(i-m+1);
       }
       return ans;
    }
    // ================= 代码实现结束 =================

     

     

    展开全文
  • 方法一:如果Oracle版本...第三个是标识从第几个字符开始正则表达式匹配。(默认为1) 第四个是标识第几个匹配组。(默认为1) 第五个是是取值范围: i:大小写不敏感; c:大小写敏感; n:点号 . 不匹配换行...
    方法一:

    如果Oracle版本不是太低的话,使用 正则表达式函数 REGEXP_SUBSTR 处理。

    REGEXP_SUBSTR有5个参数,分别是:
    第一个是输入的字符串
    第二个是正则表达式
    第三个是标识从第几个字符开始正则表达式匹配。(默认为1)
    第四个是标识第几个匹配组。(默认为1)
    第五个是是取值范围:
    i:大小写不敏感;
    c:大小写敏感;
    n:点号 . 不匹配换行符号;
    m:多行模式;
    x:扩展模式,忽略正则表达式中的空白字符。

    例如:
    SELECT REGEXP_SUBSTR('ABC123BCD456','[0-9]+') FROM DUAL;
    --返回123

    SELECT REGEXP_SUBSTR('ABC123BCD456','[0-9]+',6) FROM DUAL;
    --返回3

    SELECT REGEXP_SUBSTR('ABC123BCD456','[0-9]+',7) FROM DUAL;
    --返回456

    SELECT REGEXP_SUBSTR('ABC123BCD456','[0-9]+',1,2) FROM DUAL;
    --返回456

    方法二:

    使用方法一只能截取其中其中的一段数字,如果想截取字符串中的所有数据,可以使用translate函数实现,具体使用方法如下:

    select translate('&str' , '0123456789' || '&str' , '0123456789') from dual;

    translate函数语法是TRANSLATE(string,from_str,to_str),

    其功能是返回将(所有出现的)from_str中的每个字符替换为to_str中的相应字符以后的string。TRANSLATE 是 REPLACE 所提供的功能的一个超集。如果 from_str 比 to_str 长,
    那么在 from_str 中而不在 to_str 中的额外字符将从 string 中被删除,因为它们没有相应的替换字符。to_str 不能为空。Oracle 将空字符串解释为 NULL,并且如果TRANSLATE
    中的任何参数为NULL,那么结果也是 NULL。

    转载于:https://www.cnblogs.com/AzikPhil/archive/2012/06/12/note_oracle_exp.html

    展开全文
  • NUMPAGES Java实现字符串的匹配 广州疯狂软件学院拥有大课程体系包括java课程android课程ios课程本月基础强化营(可先就业后付款)火热报名中欢迎有志之士电话020-28309358或者QQ544627560咨询 假设我们有一一定...
  • 假设我们有一一定数的字母组成字串,我给每字母分配一素数,2开始,往后类推。这样A将会是2,B将会是3,C将会是5,等等。现在我遍历字串,把每字母代表的素数相乘。你最终会得到一很大的整数,...

    广州疯狂软件学院拥有三大课程体系包括:java课程,android课程,ios课程,疯狂软件年终钜惠,报名java就业班,免费赠送基础班,名额有限,本月火热报名中,欢迎有志之士电话或者QQ咨询。

    假设我们有一个一定个数的字母组成字串,我给每个字母分配一个素数,从2开始,往后类推。这样A将会是2,B将会是3,C将会是5,等等。现在我遍历第一个字串,把每个字母代表的素数相乘。你最终会得到一个很大的整数,对吧?

    然后--轮询第二个字符串,用每个字母除它。如果除的结果有余数,这说明有不匹配的字母。如果整个过程中没有余数,你应该知道它是第一个字串恰好的子集了。

    思路总结如下:

    1.定义最小的26个素数分别与字符'A'到'Z'对应。

    2.遍历长字符串,求得每个字符对应素数的乘积。

    3.遍历短字符串,判断乘积能否被短字符串中的字符对应的素数整除。

    4.输出结果。

    至此,如上所述,上述算法的时间复杂度为O(m+n),时间复杂度最好的情况为O(n)

    package contcurrentandalgorithm;

    /**

    *

    * @author Administrator

    */

    public class SushuStringFind {

    public static void main(String[] args) {

    int primeNumber[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,61, 67, 71, 73, 79, 83, 89, 97, 101};

    String strOne = "ABCDEFGHLMNOPQRS";

    String strTwo = "ABCDEFGHL";

    // 这里需要用到大整数

    int product = 1; //大整数除法的代码,下头给出。

    // 遍历长字符串,得到每个字符对应素数的乘积

    for (int i = 0; i < strOne.length(); i++) {

    int index = strOne.charAt(i) - 'A';

    product = product * primeNumber[index];

    }

    // 遍历短字符串

    for (int j = 0; j < strTwo.length(); j++) {

    int index = strTwo.charAt(j) - 'A';

    // 如果余数不为0,说明不包括短字串中的字符,跳出循环

    if (product % primeNumber[index] != 0) {

    break;

    }

    if (strTwo.length() == j) //cout 《 "true" 《 endl;

    {

    System.out.println("true");

    } else //cout 《 "false" 《 endl;

    {

    System.out.println("false");

    }

    }

    }

    }

    疯狂软件java培训、ios培训新年钜惠,报名Java就业班免费赠送java基础班,报名iOS就业班免费赠送iOS基础班,本月火速抢座中,为回报广大新老学员,值此新年之际推出报读就业班赠送基础班的活动

    -----------------------------------2014年初活动--------------------------------------

    疯狂软件Java学习班方向:

    1.报读JavaEE就业班赠送价值2200元基础班课程。

    2.开班一次性(一个月内)交清JavaEE就业班学费9800元,赠送基础班全套课程。

    读完基础班后不再读就业班,无条件退还剩余学费。

    疯狂软件iOS学习班方向:

    1.报读iOS应用+手游就业班赠送价值1800元iOS基础班课程。

    2.开班一次性(一个月内)交清iOS应用+手游就业班就业班学费7800元,赠送基础班全套课程。

    展开全文
  • 1、主串S一位开始,S与T前三个字母匹配成功,但是S四个字母是d而T的是g。一位匹配失败。下图所示,其中竖直连线表示相等,闪电状弯折线表示不相等。 ![在这里插入图片描述]...

    模式匹配:子串定位运算,在主串中找出子串出现的位置。

    假设我们要从下面的主串S=“goodgoogle”中,找到T=“google”这个子串的位置。我们通常需要下面的步骤。

    1、主串S第一位开始,S与T前三个字母匹配成功,但是S第四个字母是d而T的是g。第一位匹配失败。下图所示,其中竖直连线表示相等,闪电状弯折线表示不相等。
    在这里插入图片描述
    2、主串S第二位开始,主串S首字母是o,要匹配的T首字母是g,匹配失败。
    在这里插入图片描述
    3、主串S从第三位开始,主串S首字母是o,要匹配的T首字母是g,匹配失败。
    在这里插入图片描述
    4、主串S第四位开始,主串S首字母是d,要匹配的T首字母是g,匹配失败。
    在这里插入图片描述
    5、主串S第五位开始,S与T,6个字母全匹配,匹配成功。
    在这里插入图片描述
    简单的说,就是对主串的每一个字符作为子串开头,要与匹配的字符串进行匹配。对主串做大循环,每个字符开头做T的长度的小循环,直到匹配成功或者全部遍历完成为止。

    //返回子串T在主串S中第pos个字符之后的位置。若不存在,返回0
    //T非空,1<=pos <=StrLength(S)
    int Index(Sitnrg S,String T,int pos)
    {
    	/*
    	i用于主串S中当前下标位置,若pos不为1,则从pos位置开始匹配
    	*/
    	int i = pos;
    	int j = 1; //j用于子串T中当前位置下标值
    
    	while(i <= S[0] && j <= T[0]) //i小于长度且j小于T的长度时循环
    	{
    		if(S[i] == T[i])  //字母相等则继续
    		{
    			++i;
    			++j;
    		}
    		else
    		{
    			i = i - j+ 2; //退回到上次匹配首位的下一位
    			j = 1;       //j退回到子串T的首位
    		}
    	}
    	if(j > T[0])
    		return i - T[0];
    	else
    		return 0;
    }
    

    分析一下,最好的情况就是一开始就匹配成功,时间复杂发为O(1),最坏的情况就是每次匹配不成功的匹配都发生在串T的最后一个字符。

    展开全文
  • KMP字符串匹配

    2021-01-17 18:35:42
    第三行输入整数M,表示字符串S的长度。 第四行输入字符串S。 输出格式 共一行,输出所有出现位置的起始下标(下标0开始计数),整数之间用空格隔开。 数据范围 1≤N≤105 1≤M≤106 ...
  • 大致题意是给你n开始的s个连续的数字,例如n=15,s=3,那么对应16、17、18三个数字。然后,每个数字的可行放法是放在它的因子对应的位置上,例如8可以放到1、2、4、8个位置上。问你是否存在一种摆法使得这s个数字...
  • Oracel 提取数字

    2019-09-22 01:17:08
    5个参数第一个是输入的字符串第二个是正则表达式第三个是标识从第几个字符开始正则表达式匹配。(默认为1)第四个是标识第几个匹配组。(默认为1)第五个是是取值范围:i:大小写不敏感;c:大小写敏感;n:点号 . ...
  • 1.jQuery完成下拉列表:    以每一个匹配的元素作为上下文来执行一函数。...而且,在每次执行函数时,都会给函数传递一表示作为执行环境的元素在匹配的元素集合中所处位置的数字值作为参数(开始的...
  • n+b这种形式的表达式,可以选中b个开始的所有子元素。 例如 :nth-child(n+4) 将会选中除了一、二、个子元素之外的所有子元素。 li:first-child:nth-last-child(n+4), li:first-child: ...
  • 擦皮,测了好长时间,真的是没基础,太可悲了,太可怕了,一定要买本书来好好看看。...评注:腾讯QQ号10000开始也就是说一位必须是非0的数字,然后我就加了{3},然后就是各种试长度了,真的是醉,太损
  • Java实现字符串的匹配

    2014-01-15 14:52:00
     假设我们有一一定数的字母组成字串,我给每字母分配一素数,2开始,往后类推。这样A将会是2,B将会是3,C将会是5,等等。现在我遍历字串,把每字母代表的素数相乘。你最终会...
  • 给定一模式串S,以及一模板串P,所有字符串中只包含大小写英文字母...第三行输入整数M,表示字符串S的长度。 第四行输入字符串M。 输出格式 共一行,输出所有出现位置的起始下标(下标0开始计数),整数...
  • 第四是标识从第字符开始正则表达式匹配。(默认为1) 第五是标识第几个匹配组。(默认为全部都替换掉) 第六是是取值范围: i:大小写不敏感; c:大小写敏感; n:点号 . 不匹配换行符号; m:多行模式;...
  • 第三行输入整数M,表示字符串S的长度。 第四行输入字符串S。 数据范围: 1≤N≤1041≤N≤10^41≤N≤104 1≤M≤1051≤M≤10^51≤M≤105 输出描述 共一行,输出所有出现位置的起始下标(下标0开始计数),整数之间用...
  • 分割开始,有了另一方向——输入图像输出是某些属性。 灰度图像的分割,分为两类:(1)根据灰度的不连续性,进行边缘分割;(2)根据灰度相似性,把图像分割为几相似的区域。 1)不连续性—点、线、面,可以...
  • Perl 实例精解(第三版).pdf

    热门讨论 2010-11-06 09:08:02
    对每主题都使用了范例说明,Perl变量、正则表达式,到编写报表、CGI脚本和网络应用,并对范例程序进行了解释。读者可以很容易地通过这些范例掌握Perl语言的语法。附录含有完整的函数和定义、命令行开关、特殊...
  • REGEXP_SUBSTR有5个参数,分别是:第一个是输入的字符串第二个是正则表达式第三个是标识从第几个字符开始正则表达式匹配。(默认为1)第四个是标识第几个匹配组。(默认为1)第五个是是取值范围:i:大小写不敏感;c:大...
  • 实际上,程序该点开始执行并继续越过case边界直到switch语句结束。例如,下面记录元音字母数的switch程序的实现就是不正确的: #include "stdafx.h" #include <iostream> #include "s...
  • 本书总结了十几本c++图书及教材的优点,摈弃了它们语言拖沓、层次结构混乱等缺陷,开始、由浅入深、层层递进、细致而又详尽地讲解c++这门大型编程语言。.  本书知识系统全面,拥有字典般的容量,可随用随查,...
  • 一行包含三个整数N,M,T,其中T表示禁止放置的格子的数量。 接下来T行每行包含两个整数x和y,表示位于x行y列的格子禁止放置,行列数1开始。 输出格式 输出一个整数表示结果。 数据范围 1≤N,M≤100 输入样例...
  • 从第几个字符开始, 要找到第几个匹配的序号)例如:INSTR('CORPORATE FLOOR','OR', 3, 2)中,源字符串为'CORPORATE FLOOR', 在字符串中查找'OR',从第三个字符位置开始查找"OR",取第三个字后第2个匹配项的位置。...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 265
精华内容 106
关键字:

从第三个字开始匹配