2014天津事业单位考试计算机基础知识：串的基本运算——子串定位(上)

字串定位的名词解释字串定位，又称为字符串定位，是计算机科学中的一个概念，用于指示在一个字串中查找特定字符或子序列的位置。

字串定位在各种计算机应用中被广泛使用，包括文本搜索、字符串匹配、数据分析等。

本文将对字串定位进行详细解释和探讨。

一、字串定位的基本概念字串定位是一种通过查找特定字符或子序列在一个目标字串中的位置来实现的技术。

在计算机中，字串是由一系列字符组成的序列，而子序列则是指从一个原始字串中提取出的一部分字符组成的新序列。

字串定位的目的是确定特定字符或子序列在目标字串中的位置，从而方便后续的处理和应用。

二、字串定位的应用领域字串定位在计算机科学的许多领域中都有重要应用。

其中最常见的应用之一是文本搜索。

在大规模的文本数据集中，如互联网上的网页、文档集合等，利用字串定位可以快速地找到包含特定关键字或短语的文本片段，实现高效的搜索功能。

另一个重要的应用是字符串匹配。

对于一个给定的模式字符串，字串定位可以帮助我们查找目标字串中是否存在与之完全或部分匹配的子序列。

这在信息提取、模式识别、数据库查询等领域中都是常见的需求。

字串定位还被广泛应用于数据分析和处理中。

比如，在处理日志文件、文本消息等大量的结构化和非结构化数据时，常常需要根据特定的字符或子序列进行过滤、分类或统计等操作，从而实现对数据的深入分析和处理。

三、字串定位的算法和方法为了实现字串定位，计算机科学家和工程师们开发了许多基于不同算法和方法的技术。

其中最常见和经典的算法之一是暴力匹配算法（Brute Force）。

暴力匹配算法是一种简单直观的方法，它通过从目标字串的第一个字符开始，逐个与待定的子序列进行比较，直到找到完全匹配的子序列或遍历完整个目标字串。

尽管这种算法的时间复杂度较高，但是对于较小规模的字串和文本数据，它仍然是一种有效的解决方案。

除了暴力匹配算法之外，还有一些更高效的算法和数据结构可以用于字串定位。

例如，KMP算法（Knuth-Morris-Pratt Algorithm）和BM算法（Boyer-Moore Algorithm）等，它们都利用了字符匹配的特性和字串的部分匹配信息，从而在实际应用中实现了更快速和高效的字串定位。

串与序列算法串和序列是计算机中非常重要的概念，它们在数据处理和算法设计中都有广泛应用。

本文将介绍串与序列算法的基本知识和相关操作。

一、串算法1. 串的定义：串是由零个或多个字符组成的有限序列，一般用字符串表示。

例如，"Hello World"就是一个由字符串构成的串。

2. 串的基本操作：串的基本操作包括串的赋值、串的拼接、串的截取、串的查找和串的比较操作等。

其中，串的赋值操作是将一个字符串赋值给一个串变量。

例如：string a = "Hello World";串的拼接操作是将两个串连接成一个新的串。

例如：string a = "Hello";string b = "World";string c = a + b; //输出Hello World串的截取操作是从一个串中截取出一段子串。

例如：string a = "Hello World";string b = a.substr(0, 5); //输出"Hello"串的查找操作是在一个串中查找另一个子串的位置。

例如：string a = "Hello World";int pos = a.find("World"); //输出6串的比较操作是比较两个串的大小关系。

例如：string a = "Hello";string b = "World";if(a < b){cout<<"a is smaller than b"<<endl;}else{cout<<"a is bigger than b"<<endl;}3. 串匹配算法：串匹配算法是指在一个串中查找另一个子串的位置，它的应用非常广泛。

天津事业单位招聘考试网
2014年天津事业单位考试专技岗计算机基础知识：
算法基础知识
【导语】在天津事业单位考试中，计算机专业知识的复习向来是考生复习备考阶段的一大重点，其中中公事业单位考试网为计算机网络知识的复习为考生提供知识点梳理，帮助考生备考!
1.算法
通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。

2.算法特性
⑴输入：一个算法有零个或多个输入(即算法可以没有输入)，这些输入通常取自于某个特定的对象集合。

⑵输出：一个算法有一个或多个输出(即算法必须要有输出)，通常输出与输入之间有着某种特定的关系。

⑶有穷性：一个算法必须总是(对任何合法的输入)在执行有穷步之后结束，且每一步都在有穷时间内完成。

⑷确定性：算法中的每一条指令必须有确切的含义，不存在二义性。

并且，在任何条件下，对于相同的输入只能得到相同的输出。

⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

以上是中公事业单位考试网为考生梳理计算机基础知识点，供大家学习识记!。

子串定位运算子串定位运算串是特殊的线性表，故顺序串和链串上实现的运算分别与顺序表和单链表上进行的操作类似。

C 语言的串库 <string.h> 里提供了丰富的串函数来实现各种基本运算，因此我们对各种串运算的实现不作讨论。

利用串函数实现串的基本运算部分内容【参见练习】。

下面讨论在顺序串和链串上实现的子串定位运算。

1 、子串定位运算子串定位运算类似于串的基本运算中的字符定位运算。

只不过是找子串而不是找字符在主串中首次出现的位置。

此运算的应用非常广泛。

【例】在文本编辑中，我们经常要查找某一特定单词在文本中出现的位置。

解此问题的有效算法能极大地提高文本编辑程序的响应性能。

子串定位运算又称串的模式匹配或串匹配。

2 、目标（串）和模式（串）在串匹配中，一般将主串称为目标（串），子串称为模式（串）。

假设 T 为目标串， P 为模式串，且不妨设：T="t 0 t 1 t 2 …t n-1 "P="p 0 p 1 p 2 …p m-1 "(0 ＜m≤n)3 、串匹配串匹配就是对于合法的位置（又称合法的位移）0≤i≤n-m ，依次将目标串中的子串"t i t i+1 …t i+m-1 " 和模式串"p 0 p 1 p 2 …p m-1 " 进行比较：① 若"t i t i+1 …t i+m-1 " ＝"p 0 p 1 p 2 …p m-1 " ，则称从位置 i 开始的匹配成功，或称 i 为有效位移。

② 若"t i t i+1 …t i+m-1 "≠"p 0 p 1 p 2 …p m-1 " ，则称从位置 i 开始的匹配失败，或称 i 为无效位移。

因此，串匹配问题可简化为找出某给定模式串 P 在给定目标串T 中首次出现的有效位移。

注意：有些应用中要求求出 P 在 T 中所有出现的有效位移。

【数据结构】【串】【课堂笔记】（含代码）串串的基本概念串是由0个或者多个字符组成的有限序列记为：s="a11a2……a n"串与线性表的对⽐串的逻辑结构：和线性表极为相似区别：串的数据对象约定是字符集串的基本操作：和线性表有很⼤区别线性表的基本操作：以单个元素为操作对象串的基本操作：以串的整体为操作对象⼦串与主串⼦串由串中任意个连续的字符组成的⼦序列主串包含⼦串的串字符位置字符在序列中的序号（从1开始）⼦串位置⼦串的⾸字符在主串中的位置串的基本操作加⼯型串复制：将某个串复制给当前串串连接：将串S1和S2联接⽽成⼀个新串串替换：⽤⼦串x替换当前串中的⼦串y插⼊⼦串：将⼦串插到当前串中的某个位置删除⼦串：从当前串中删除指定⼦串⼤写转⼩写：将串中的⼤写字母转化为对应⼩写字符⼩写转⼤写：将串中的⼩写字母转化为对应⼤写字符串压缩：将当前串中⾸部和尾部的所有空格删除引⽤型判空：判断当前串是否为空串⽐较：判断当前串与指定串是否相等求串长：返回当前串的字符个数求⼦串：返回串的第i个字符开始的长达k个字符的⼦串⼦串定位：输出⼦串在当前串中⾸次出现的位置串的顺序储存与实现在串的顺序储存中，⼀般有三种⽅法表⽰串的长度（1）⽤⼀个变量来表⽰串的长度（2）在串尾储存⼀个特殊字符作为串的终结符（3）⽤数组的0号存在串的长度串的实现顺序储存结构的串可以⽤字符数组来存储字符数据串的初始化public calss string{private int maxSize =10;//串中字符数组的初始长度private char[] chars;//存储元素的数组对象private int length;//保存串的当前长度public string(){}public string(int n){}public void copy(string t){}public boolean isEmpty(){}public int compare(string t){}public int getLength(){}...//此处省略部分成员⽅法}getter and setterpublic class string {private int maxSize =10;//串中字符数组的初始长度private char[] chars;//存储元素的数组对象private int length;//保存串的当前长度public string(){}public string(int n){}public void copy(string t){}public boolean isEmpty(){return length <= 0;}public int compare(string t){return -1;}public int getLength(){return length;}public int getMaxSize() {return maxSize;}public void setMaxSize(int maxSize) {this.maxSize = maxSize;}public char[] getChars() {return chars;}public void setChars(char[] chars) {this.chars = chars;}public void setLength(int length) {this.length = length;}}功能完善import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;public class string {private int maxSize =10;//串中字符数组的初始长度private char[] chars;//存储元素的数组对象private int length;//保存串的当前长度//串的初始化//构造⼀个空串public string(){}//构造⼀个能保存n个字符串的串public string(int n){}public void copy(string t){//将串t复制给当前串if(this.maxSize<t.maxSize){this.maxSize=t.maxSize;this.chars = new char[this.maxSize];}this.length=0;//初始化当前串的长度for(int i=0;i<t.getLength();i++){this.chars[i]=t.chars[i];this.length++;}}public boolean isEmpty(){return length <= 0;}/*** compare 串⽐较* @param t 字符型* @return int型 | 若当前串等于串t，则返回值0；若当前串⼤于串t，则返回1；若当前串⼩于于串t，则返回-1 * @author xrilang*/public int compare(string t){int i = 0;while(this.chars[i]==t.chars[i] && i < this.length && i<t.getLength()){i++;}//若当前串等于串t，则返回值0if(i==this.length && i==t.length) return 0;//若当前串⼤于串t，则返回1else if(i==t.getLength() && i < this.length) return 1;//若当前串⼩于于串t，则返回-1else return -1;}/*** concat 串联结* @param t 字符型* @author 萌狼蓝天*/public void concat(string t){if(this.maxSize<this.length+t.getLength()){//当前串容量不够，暂存到数组tempArrchar[] tempArr = new char[this.length];for(int i=0;i<this.length;i++){tempArr[i]=this.chars[i];}//重设maxSize，使串容量满⾜需求this.maxSize = this.length+t.getLength();this.chars=new char[this.maxSize];//恢复当前串的原始状态for(int i=0;i<tempArr.length;i++){this.chars[i]=tempArr[i];}}for(int i=0;i<t.length;i++){this.chars[this.length]=t.chars[i];this.length++;}}/*** subString 求⼦串* @param pos int型索引所求⼦串起始位置,不能为负数* @param len int型长度所求⼦串的长度* @return string型返回所求⼦串，如果不存在则返回null* @author 萌狼蓝天*/public string subString(int pos,int len){if(pos<0) return null;if(pos+len>=this.length) {//从位置pos开始不存在长度为len的⼦串 return null;}string temp = new string(len);for(int i=0;i<len;i++){temp.chars[i]=this.chars[pos+i];temp.length ++;}return temp;}public int getLength(){return length;}public int getMaxSize() {return maxSize;}public void setMaxSize(int maxSize) {this.maxSize = maxSize;}public char[] getChars() {return chars;}public void setChars(char[] chars) {this.chars = chars;}public void setLength(int length) {this.length = length;}}。

多字符串查找子串算法1.引言1.1 概述在现代计算机科学中，字符串处理是一个非常重要的研究领域。

字符串的操作和查找在各种应用中被广泛使用，例如文本编辑、搜索引擎、数据库以及信息提取等。

其中，查找字符串的子串是一种常见的操作，其应用范围涉及到很多领域。

多字符串查找子串算法是一种用于在多个字符串中查找指定子串的技术。

在实际应用中，常常会遇到需要同时查找多个字符串中的子串的情况，例如在搜索引擎中同时对多个网页进行关键词的查找。

本文将介绍多字符串查找子串算法的一些常见方法和技术。

通过对这些算法的探讨和分析，旨在提供给读者一个全面了解和掌握多字符串查找子串算法的知识，以便能够在实际应用中更好地应用这些算法。

本文的结构如下：首先，将给出对多字符串查找子串算法的定义和背景介绍，让读者对该领域有一个整体的认识。

接着，将详细介绍一些常见的多字符串查找子串算法，包括暴力匹配算法、KMP算法、Boyer-Moore算法等。

将对每个算法的原理、实现步骤和时间复杂度进行详细讨论。

在本文的结尾部分，将对多字符串查找子串算法进行总结，并展望其未来的发展。

同时，还将提出一些可能的改进和优化方向，以便读者在实际应用中能够更加高效地使用多字符串查找子串算法。

希望通过本文的阅读，读者能够对多字符串查找子串算法有一个全面的了解，并能够在实际应用中灵活运用这些算法，从而提高工作效率和准确性。

同时也希望能够激发读者对多字符串查找子串算法研究的兴趣，为该领域的进一步发展贡献力量。

文章结构部分的内容可以按照以下方式编写：1.2 文章结构本文将按照以下结构来探讨多字符串查找子串算法的相关内容：1. 引言：首先介绍本文的研究背景和动机，解释多字符串查找子串算法的重要性和应用领域。

2. 正文：主要分为两个部分：2.1 子串的定义和应用：详细介绍什么是子串以及在实际应用中子串的常见应用场景。

探讨子串在文本处理、数据分析等领域的重要性，并举例说明。

2.2 常见的多字符串查找子串算法：深入探讨多字符串查找子串的算法，包括但不限于暴力匹配算法、KMP 算法、Boyer-Moore 算法等。

1上机实训3：串的基本操作一、实训目的通过实训，掌握串的运算（赋值，比较，联结，插入子串，模式匹配……等）二、实验理论知识1)串的基本概念及其含义串( string)是由零个或多个字符组成的有限序列，一般记作:s='a1a2…an'(n≥0)，其中s为串的名字，用单引号括起来的字符序列为串的值；ai(1≤i≤n)可以是字母、数字或其它字符（取决于程序设计语言所使用的字符集）；n为串中字符的个数，称为串的长度。

2)串的存储表示及其实现●顺序存储可以用一组地址连续的存储单元依次存放串的各个字符，这是串的顺序存储结构，也称为顺序串●链式存储和线性表的链式存储结构相类似，也可采用链表方式存储串值。

串的这种链式存储结构简称为链串。

用链表存储字符串，每个结点需要有两个域：一个数据域（data）和一个指针域(Next)，其中数据域存放串中的字符，指针域存放后继结点的地址。

3)模式匹配问题三、实训案例与分析【实例1】串的存储与基本运算【实例分析】在本实例中练习计算字符串的长度、字符串的复制、字符串的比较、字符串的连接、字符串的插入等基本操作。

在设计时1)编写一个菜单函数，根据不同情况做（1-5）不同选择。

2)如果选择1，即要求计算输入字符串的长度。

3)如果选择2，完成字符串的复制。

4)如果选择3，完成字符串的比较。

5)如果选择4，完成两个字符串的连接。

6)如果选择5，字符串的插入。

【参考程序】#include <stdio.h>#define MAX 128typedef enum {fail,success} status;typedef enum {false,true} boolean;main(){ int strlen();void strass();boolean strcmp();status strcat( );status strins();int t,n,i;boolean b;status st;char s[MAX],s1[MAX],s2[MAX];printf("\n1. The length of string\n");printf(" 2. The assignment of string\n");printf(" 3. A string compare with another string:\n"); printf(" 4. A string connect with another string:\n"); printf(" 5. A string to be inserted into another string\n"); printf(" Please input a operation:");/*输入操作选项*/ scanf("%d",&t);switch(t){case 1:printf("please input a string:\n");getchar();gets(s);n=strlen(s);printf("the length is: %d",n);break;case 2:printf("please input the first string:\n");getchar();gets(s1);printf("please input the second string:\n");getchar();gets(s2);strass(s1,s2);break;case 3:printf("please input the first string:\n"); getchar();gets(s1);printf("please input the second string: \n"); gets(s2);b=strcmp(s1,s2);if (b==true)printf("equal\n");elseprintf("not equal\n");break;case 4:printf("please input the first string:\n"); getchar();gets(s1);printf("please input the second string:\n"); gets(s2);st=strcat(s1,s2);if(st==success)printf("answer is %s\n",s1);elseprintf("error!\n");break;case 5:printf("please input the first string:\n"); getchar();gets(s1);printf("please input the second string:\n"); gets(s2);printf("please input i:");scanf("%d",&i);st=strins(s1,i,s2);if(st==success)printf("answer is: %s\n",s1);else printf("error!\n");break;case 0:break;default: printf("There isn't this operation!");}}int strlen(s) /*求字符串的长度子函数*/char s[];{ int i;for(i=0;s[i]!='\0';i++);return (i);}void strass(s1,s2)char s1[],s2[];{ int i=0;while(s1[i]!='\0'){ s2[i]=s1[i];i++;}s2[i]='\0';printf("s2 is %s",s2);}boolean strcmp(s1,s2) /*字符串比较子函数*/ char s1[],s2[];{ int i=0;while (s1[i]==s2[i] && s1[i]!='\0' && s2[i]!='\0') i++;if (s1[i]=='\0' && s2[i]=='\0')return (true);elsereturn (false);}status strcat (s1,s2) /*字符串连接子函数*/char s1[],s2[];{ int i,j,k;i=strlen(s1);j=strlen(s2);if((i+j)>=MAXN)return(fail);for(k=0;k<=j;k++)s1[i+k]=s2[k];return (success);}status strins (s1,i,s2)char s1[],s2[];int i;{ int m,n,k;m=strlen(s1);n=strlen(s2);if (i<0||i>m||(m+n)>MAXN )return (fail) ;for(k=m;k>=i;k--)s1[k+n]=s1[k];for(k=0;k<n;k++)s1[i+k]=s2[k];return (success);}【测试数据与结果：】计算字符串的长度1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another string Please input a opertation:1please input a string:you are a boy!the length is: 14字符串的复制1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another string Please input a opertation:2please input the first string:you are a boy!please input the second string:i am a girl!s2 is you are a boy!字符串的比较1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another string Please input a opertation:3please input the first string:you are a boy!please input the second string:i am a girl!not equal字符串的连接1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another stringPlease input a opertation:4please input the first string:you are a boy!please input the second string:i am a girl!answer is：you are a boy!i am a girl!字符串的插入1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another stringPlease input a opertation:5please input the first string:you are a boy!please input the second string:i am a girl!please input i:2answer is i am a girl! you are a boy!【实例2】统计主串指定单词在主串中出现的次数和位置【实例描述】统计主串指定单词在主串中出现的次数和位置，要求：1)输入以回车作为结束符的一串字符作为主串；2)求主串中指定单词出现的次数和位置，注意单词与子串的区别；【实例分析】假设num存放出现次数，初始化为0，position[i]存放每一次匹配时的位置。

第四章串★本章主要讲授内容1、串的定义和基本操作2、串的顺序存储结构3、串的链式存储结构4、模式匹配算法及其改进算法★★课时分配：1、2，两个学时，3两个学时, 4 四个学时，上机6个学时★★★重点、难点：模式匹配及其算法第一节．串的定义和基本运算串是字符串的简称。

它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。

串一般记作：s= "a1a2...an" (n30)其中，s是串的名称，用双引号（""）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。

当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。

s1= ""s2= " "s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。

概念：子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。

包含子串的串又被称为该子串的主串。

例如，有下列四个串a，b，c，d：a= "Welcome to Beijing"b= "Welcome"c= "Bei"d= "welcometo"子串的位置：子串在主串中第一次出现的第一个字符的位置。

两个串相等：两个串的长度相等，并且各个对应的字符也都相同。

例如，有下列四个串a，b，c，d：a= "program"b= "Program"c= "pro"d= "program "串的基本操作：（1）创建串StringAssign (s,string_constant)（2）判断串是否为空StringEmpty(s)（3）计算串长度Length(s)（4）串连接Concat(s1,s2)（5）求子串SubStr(s1,s2start,len)（6）串的定位Index(s1,s2)例如1：将s2串插入到串s1的第i个字符后面。

字符串与子串的包含关系字符串和子串的包含关系在计算机科学中是一个非常基本的概念，尤其在字符串处理和算法中有着重要的应用。

在本文中，我们将介绍字符串和子串的概念、常见的字符串匹配算法、以及如何判断字符串和子串是否包含的一些常见方法。

字符串和子串的概念在计算机科学中，字符串是指由零个或多个字符组成的有限序列，通常用来表示文本的数据结构。

字符串中的字符可以是字母、数字、符号等，也可以是特殊的字符（如换行符、制表符等）。

子串则是指在一个字符串中连续的一段字符序列，也称为子序列。

例如，在字符串“hello world”中，“hello”、“world”和“lo w”就是它的三个子串。

字符串匹配算法字符串匹配是指在一个字符串中查找另一个字符串或者子串的过程。

它是计算机科学中的一个基本问题，有着广泛的应用。

常用的字符串匹配算法有以下几种：1.暴力匹配算法暴力匹配算法是最简单、最朴素的字符串匹配算法。

它的基本思路是：先定位到字符串的起始位置，然后在字符串中逐个字符地比较，直到找到与目标子串相同的位置。

如果遍历完整个字符串都没有找到，说明目标子串不存在。

暴力匹配算法的时间复杂度为O(n*m)，其中n是字符串的长度，m是目标子串的长度。

这种算法的优点是实现简单，缺点是效率较低，对于大规模字符串的匹配不太适用。

2.KMP算法KMP算法（Knuth-Morris-Pratt Algorithm）是一种基于前缀匹配的字符串匹配算法。

它的基本思路是：当在字符串s中查找某个目标子串p时，如果发现s的某一位与p的某一位不匹配，那么就利用之前已经计算好的前缀匹配数组来跳过前面已经匹配好的部分，从之前匹配失败的位置之后继续匹配。

3.Boyer-Moore算法Boyer-Moore算法是另一种经典的字符串匹配算法。

它的基本思路是：从目标子串的末尾开始向前匹配，根据不匹配位置的字符在子串中出现的位置，跳过一些已经匹配的部分，从而加快查找速度。