DS_string

数据结构之串

欢迎来到简单而又复杂的串世界,博主许久没有去研究串，还停留在以前学习和使用串的水平，再来一波学习和归纳，发现串的基本用法其实简单，也好理解，但是衍生出来的和应用相关，而且复杂，下面道来；

串的基本

串的定义

“a1a2…..an”,其中包含字母，广义上可以是任意字符
在c/c++中结尾带’\0’，python则不带，长度均不包含’\0’
串长度-不同编码不同，根据具体需要如字节，实际字符等
空串和空白串，空白又可能是tab,回车，空格等等“
串的子串:子串个数：n(n+1)/2–等差数列，
串常用的数据结构

串常量–存在从汇编去看－数据段(data)

    .file	"test.c"
	.section	.rodata
.LC0:
	.string	"kesance"
.LC1:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function

串数组:
将字符串存在顺序数组中
堆分配存在链表中
字符串常用函数
子串个数：
串赋值
串比较
求串长
串拼接
求子串
替换子串
定位子串的位置
字符编码和字符串匹配
字符串的编码
所谓字符编码，就是将字符用二进制唯一表示。在计算机的世界里不是1就是0，无论什么字符最后存入的还是二进制数，只是从内存中读出来时解析不同而已，即如让计算机将读出来的00111000解析成数字8,如文本显示程序，当设定为某种编码时，将字节流解析成对应的字符～现在看到的许多字体库也是这样的，将一串二进制串和某个字体对应起来，解析程序负责处理匹配和显示等
https://en.wikipedia.org/wiki/Unicode　unicode编码了解一下

传统模式匹配算法

模式匹配，就是在字符串里面匹配另一个串相似或者相同的子串，传统的想法也和一般人想到的一样，扫描并一个一个字符对比，若第二串失配，则第二串重新匹配第一串的第二个，接着往下。。

KMP算法

kmp作为完全匹配算法中的高效算法，基本原理如下：ps:大学学这个算法只学了它是什么原理，还没去想为什么这么做等）

基本思想：从上面看传统的匹配算法：

1
2
3

a b c a e f g 
a b d a e f```
像上面的字符串匹配，第一次失配的地方是在c,则按照传统的方式，则应该重新：

a b c a e f g
a b d a e f ```
但是其实如果是我们人去做匹配时，则会直接从：

    a b c a e f g
          a b d a e f ```
 开始匹配，而kmp的基本思想也是这样；
例子：

a b c d a b c f g e
a b c e a b c t
第一次失配在d,那下一次应该在
a b c d a b c f g e
a b c e a b c t```

所以它分为两部分，１是模式串在移动时候遵循的基本原理，２是当失配时，模式串的哪个位置的字符和源串的当前位置进行重新匹配；
1基本原理，重复：当模式串中存在大量的重复时，效果尤为明显
a b c d a b c e f g a b c d a b c t
上述例子一样，可以看到以d 为中点，前后有相同的串，abc,则显然next函数也能隐士检测到这个，所以当显然因为模式串的前后abc相等，而后abc又和源串的后abc相等，所以源串的后abc和模式串的前abc想等，自然失配时候就可以从模式串的d开始匹配起
2重点在next的计算，它决定当发生失配时，模式串如何移动：
- 假设模式串为P,j是当前模式串正在匹配的位置，源串为S,i是源串的当前位置，k是当P[j]!=S[i]时，P应该和S[i]比较的位置，以next[j]=k表示，故关键是求出next数组，显然k<j
- next如何计算得到:其实要利用前面的基本原理，
  P[0-k-1]==P[j-k~j-1]==S[i-k到i-1] (即next[j]=k)
  所以要求next[j+1]=?
-若P[k]==P[j]
P[0-k-1]+P[k]==P[j-k~j-1]+P[j]
即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1
-若P[k]!=P[j]
我们已经知道（0，k-1）串和（j-k,j-1）串是相等的，所以可以把（0，k-1）串当做一个新的模式串，发现在新模式串中
（0，next[k]-1）串与（k-next[k],k-1）串相等，所以（j-k,j-1）中存在与（0，next[k]-1）相等的串，所以可以把j移动到next[k],继续比较和移动。
具体程序：
c //显然，next[0]=-1,此时无法向左边移动了源串模式串都要移动 next[1]=0,此时只能向左移动到0. int getnext(char *P,int next[]){ j=1,next[j]=0,k=0; while(j<sizeof(P){ if(k==0||P[j++]==P[k++]) next[j]==k;//next[j]=next[j]+1 else k=next[k]; } }

串和哈夫曼编码

霍夫曼编码是和编码相关的一个算法，是将一个串编码为二进制整数，如类似AABXBDHADFBFJD编码为1010011100011101001,而霍夫曼编码则作为转换算法，Huffman编码使得每一个字符的编码都与另一个字符编码的前一部分不同，不会出现像’A’：00， ’B’：001，这样的情况，解码也不会出现冲突。

论文查重对比的几个算法(文本相似度）

杰卡德（Jaccard）相似系数
这种相似度计算方式相对简单，原理也易于理解，就是计算单词集合之间的交集和并集大小的比例，该值越大，表示两个文本越相似。在涉及到大规模并行计算时，该方法效率上有一定的优势。
余弦（Cosine）相似度
余弦相似度是利用计算两个向量之间的夹角，夹角越小相似度越高，其公式为：
假定A和B是两个n维向量，A是[A1,A2,…,An],B是[B1,B2,B3,…,Bn],则A与B的夹角余弦等于
等等,用时再看：
https://www.cnblogs.com/huilixieqi/p/6493089.html
linux下的diff命令
还有win上的beyondcompare软件，这两个是用于比较文本的差异的，在代码移植时经常用到

串匹配－正则表达式

正则表达式用于匹配文本字符串，但是并不一定是完全匹配，且是匹配的串出现有随意性

正则表达式的理论基础

最早接触到正则表达式，是在大三学习编译原理的时候，解析词法语法的时候会用到正则表达式，用来过滤关键词，像c语言的很多关键词，以及判断它是不是合法的表达式，等等，常用的是lex和yacc,最原始的是自己的实现对词法和语法的解析，而不借助的lex；
正则表达，语法树，常用有限状态机来来实现，功能强大的如图灵机；

正则表达式和编译原理

正则表达式的基本实现

用c实现正则表达实现词法分析：
常用的正则表达式
语言支持
脚本语言支持情况
sed,awk

串和流

流，所有的文本流
流分为二进制流和文本流

数据结构之串

串的基本

串的定义

串常用的数据结构

字符串常用函数

字符编码和字符串匹配

字符串的编码