串和数组笔记总结 第1篇
串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为
其中s为串的名字，其中元素可以是字母、数字或其他字符；传中字符的数目n称为串的长度，零个字符的串称为空串，其长度为0。
在C语言中，我们常常用char s[ ]的形式来表示一个串，而在C++中当调用了头文件#include
串的存储有两种方式，顺序存储和链式存储，由于串作为一种一对一的逻辑结构（也就是线性结构），它的声明和存储模式就是一种线性表，而线性表的存储和操作已经在第二章讲的差不多了，就不再在这里赘述了。
说到串，最经典的一类题就是字符串匹配问题了，在这里放一道例题和三种解法：
这种算法最为直观，简单来说就是运用双指针对每一位进行比较，这时，时间复杂度为O（n*m）
简单来说就是在BF算法的基础上加了一点记忆化搜索，减少了重复查找一段已经确认相同的子串，使得复杂度降为O（n+m）
就是将每一段字符串看作一个高进制的数字（哈希值），然后通过匹配哈希值的方式来查找相同子串，复杂度为O（n-m），但是有时出题人可能卡哈希（即两个不同的字符串，在经过取模后哈希值相同），因此经常需要用到双哈希（据wls说双哈希也有人卡，他曾用过三哈希）。
区分一下子串和子序列的概念：子串指的是串中连续的某一段；子序列则指的是需要按照串的序列但是不一定要连续的串。
另外，在串中的比较我们通常说的是字典序比较。在字典中，我们查询一个单词或者一个字往往都要以它的单词（或拼音）在26个字母中的排序来查找，这也就是字典序的由来，当串中不仅仅包括字母时，它的比较往往遵循ACII表每个字符的对应值来进行比较。
在串中，空串指的是长度为0的串，而不是有空格的串，在串中，空格也被看作一个符号。
串和数组笔记总结 第2篇
子串的定位操作通常称为串的模式匹配，它求的是子串(常称模式串)在主串中的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法。
加入给定字符串ababcabcacbab，查找abcac在其主串中的位置，其相关流程如下：
图 模式匹配流程
模式匹配算法本质上是一种暴力遍历算法。在上述算法中，分别用计数指针 i 和 j 指示主串S 和模式串T中当前正待比较的字符位置。
算法思想为：
从主串S的第一个字符起，与模式T的第一个字符比较， 若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，重新和模式的字符比较；
以此类推，直至模式T 中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为与模式T中第一个字符相 等的字符在主串S中的序号，否则称匹配不成功，函数值为零。
代码实现入下：
简单的模式匹配算法的最坏时间复杂度为O(nm)，其中 n 和 m 分别为主串和模式串的长度。
KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度为O(m+n)。
next数组概念：一个字符串中最长的相同前后缀的长度加一。
图 next数组求解图
下面先直接给出KMP的算法流程：
假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符； 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即移动的实际位数为：j - next[j]，且此值大于等于1。
要了解子串的结构,首先要弄清楚几个概念:前缀、后缀和部分匹配值。
前缀指除最后一个字符以外,字符串的所有头部子串;
后缀指除第一个字符外,字符串的所有尾部子串;
部分匹配值则为字符串的前缀和后缀的最大公共前后缀长度。
举如下简单例子： 字符串 abcdab 前缀的集合：{a,ab,abc,abcd,abcda} 后缀的集合：{b,ab,dab,cdab,bcdab} 那么最长相等前后缀即为ab，最长部分匹配值就为2 字符串：abcabfabcab中最长相等前后缀是abcab，最长部分匹配值就为5
再比如 ′ababa′ ′a′ 的前缀和后缀都为空集最大公共前后缀长度长度为0。 ′ab′ 的前缀为 { a } ,后缀为 { b } , { a } ∩ { b } = NULL，最大公共前后缀长度长度为0。 ′aba′ 的前缀为{a,ab}, 后缀为 { a , ba } , { a , a b } ∩ { a , b a } = { a }, 最大公共前后缀长度长度为1 ′abab′ ，前缀∩后缀，{a,ab,aba}∩{b,ab,bab}={ab}，最大公共前后缀长度长度为2。 ′ababa′ ，前缀∩后缀，{a,ab,aba,abab}∩{a,ba,aba,baba}={a,aba}, 公共元素有两个,最大公共前后缀长度长度为3。
回到最初的问题,主串为′abacabcacbab′,子串为′abcac′。 利用上述方法容易写出子串′abcac′的最大公共前后缀长度为00010,将最大公共前后缀长度值写成数组形式,就得到了最大公共前后缀长度(Partial match,PM)的表。
图 最大公共前后缀长度
在这里插入图片描述 下面用PM表来进行字符串匹配：
第一趟匹配过程: 发现 c与a不匹配，前面的2个字符′ab′是匹配的，查表可知，最后一个匹配字符b对应的部分匹配值为0，因此按照下面的公式算出子串需要向后移动的位数:移动位数=已匹配的字符数−对应最大公共前后缀长度 因为2−0=2，所以将子串向后移动2位。
如下进行第二趟匹配: 第二趟匹配过程: 发现 c与 b不匹配，前面4个字符′abca′是匹配的，最后一个匹配字符a对应的部分匹配值为4−1=3，将子串向后移动3位。
如下进行第三趟匹配:
第三趟匹配过程: 子串全部比较完成，匹配成功。整个匹配过程中，主串始终没有回退，故KMP算法可以在O(n+m)的时间数量级上完成串的模式匹配操作，大大提高了匹配效率。
某趟发生失配时，如果对应的部分匹配值为0，那么表示已经匹配相等序列屮没有相等的前后 缀，此时移动的位数最大，直接将了串首字符后移到主串i位置进行下一趟比较；如果已匹配相 等序列中存在最大相等前后缀（可理解为首尾重合），那么将子串向右滑动到和该相等前后缀对 齐（这部分字符下一趟显然不需要比较）,然后从主串的i位置进行下一趟比较。
使用部分匹配值时,每当匹配失败,就去找它前一个元素的部分匹配值,这样使用起来有些不方便,所以将PM表右移一位,这样哪个元素匹配失败,直接看它自己的部分匹配值即可。将上例中字符串′abac′的PM表右移一位,就得到了next数组
我们注意到：
有时为了使公式更加简洁、计算简单，将next数组整体+1。
因此，上述子串的next数组也可以写成
最终得到子串指针变化公式 j =next[j]。 next[ j ]的含义是:在子串的第j个字符与主串发生失配时,则跳到子串的next[ j ]位置重新与主串当前位置进行比较。
通过分析，可以知道，除第一个字符外，模式串中其余的字符对应的next数组的值等于其最大公共前后缀长度加上1
前面定义的next数组在某些情况下尚有缺陷，还可以进一步优化。子串 ′aaaab′在和主串′aaabaaaaab′进行匹配时:
显然后面3次用一个和p4相同的字符跟S4比较毫无意义，必然失配。 比较毫无意义。那么如果出现了这种类型的应该如何处理呢? 如果出现了，则需要再次递归，将next[j]修正为 next[next[j]],直至两者不相等为止，更新后的数组命名为nextval。计算next数组修正值的算法如下，此时匹配算法不变。
简单来说。它是在计算出next值的同时，如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next的值。
串和数组笔记总结 第3篇
直接上例子：
这里的this，就非常灵性，指向的自然是相对应的k值，this运行在那个对象下，就指向那个对象。
注意函数是否带括号！！！
函数带括号的相当于调用函数： var o1 = { age:18, fun:function () { (); } } var o2 = { age:16, fun:(), } (); 上面得到的结构就是18，因为这是调用完成后的结果。
没有带括号的函数： var o1 = { age:18, fun:function () { (); } } var o2 = { age:16, fun:, //只是把o1的键值对中的值，给传递过来了。 } (); 这里没有带括号，结果就是16，因为fun函数没有被调用执行。 这里的fun:就等于 fun:function () { (); } 只是把键值对中的值转递过来了，并没有调用。
遍历语法格式：
for … in for(键 in 对象) for 例如：
for … in … 循环不仅可以遍历对象，还可以遍历数组。
删除属性语法格式：
删除属性：delete 例如：
这里介绍以下三种原始类型： 数值，字符串，布尔 原始类型的数据在一定条件下可以自动转为对象，这就是包装对象。
例如：
上面的结果就是Number {123}。
原始值，可以自动当作对象来调用，因此可以调用各种属性以及方法。 如果包装对象使用完成，会自动立即销毁。
例如：
这里记录几个很常用的：
() // 函数取绝对值
() //函数返回一个浮点数，范围在[0,1)之间。 公式：取2到8之间的数字 ()*( 8 - 2 ) + 2 获取 n - m 之间的随机数值 () * (m - n) + n 往后取特定的范围都这样取值！！！
() //返回小于或等于一个给定数字的最大整数。
实例化构造函数获取时间对象
这里显示的是中国标准时间。 var date = new Date(); (date);
这里显示的是毫秒。 var date2 = (); (date2);
获取特a定的年月日小时等。 var date3 = new Date(); (()); //获取当前小时 (()); //获取当前日 (); //获取年份 (() + 1); //获取月份 这里强调一下，JS中月份的数组是从0开始的，所以要+1。 JS中获取的时间是计算机本地时间。
使用push()方法向数组里面最后一个添加元素：
使用pop()方法删除最后一个元素：
使用slice()方法，由begin和end(不包括end),这里只是提取了一部分，原数组不变：
使用concat()方法，来合并数组：
使用join()方法和分隔符来将所有数组中的元素连接成字符串：
使用foreach()方法对数组的每一元素执行一次提供的函数。
举例学一些常用的：
substr(start , Length)方法返回一个字符串中从指定位置开始到指定字符数的字符。
上面就是从索引为2的位置开始的后5位。
toLowerCase()方法，将所有字符转换为小写。 toUpperCase()方法，将所有字符转换为大写。
replace(‘被替换’ , ‘要替换’)方法，替换字符或字符串。
trim()方法会从一个字符串的两端删除空白字符。
以下是一个查询JS的一些相关内函数和语句的网站，可以看看：
这个网站必备的！
串和数组笔记总结 第4篇
下面是创建时间Date的三种方式，了解一下：
html事件有很多：
串和数组笔记总结 第5篇
概念引入：
基本概念：
串( string)是由零个或多个字符组成的有限序列，又名叫字符串。 一般记为： S=′a1a2...an′(n>=0)。 其中， S 是串名，单引号括起来的字符序列是串的值; an 可以是字母、数字或其他字符;串中字符的个数 n称为串的长度。
其他概念： 空串： n=0 时的串称为空串。空格串：是只包含空格的串。注意它与空串的区别，空格串是有内容有长度的，而且可以不止一个空格。子串与主串：串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。子串在主串中的位置就是子串的第一个字符在主串中的序号。
串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。
在基本操作上,串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象，如查找、插入或删除某个元素等;而串的基本操作通常以子串作为操作对象，如查找、插入或删除一个子串等。