今天闲鱼有买家问我svg能不能写，给我发来了需求：

![image-20220314215027965](https://s2.loli.net/2022/03/14/sITvRqj8nprKa6O.png)

一番百度必应之后，咱就试着写写吧。





构思：页面有一个输入框、提交按钮和一个div（用来展示svg），点击按钮后获取输入框的值。

```html
<input type="text" name="inp" id="inp">
<button id="btn">确定</button>
<div class="box"></div>
```

获取输入框的值很好办，给按钮加一个`onclick`监听来得到`input`的`value`即可

```javascript
function handleSubmit() {
    let input = document.getElementById('inp')
    let value = input.value
    console.log(value)
}
document.getElementById('btn').onclick = handleSubmit
```

测试运行确认可以在控制台输出得到的值即可

接下来创建一个800*600的svg画布

```javascript
let svgNS = "http://www.w3.org/2000/svg"
let div = document.querySelector('.box')
function createTag(tag, obj) {
    var oTag = document.createElementNS(svgNS, tag)
    oTag.setAttribute('id', 's') // 这里为svg标签添加一个id，方便后续清空
    for(var attr in obj) {
        oTag.setAttribute(attr, obj[attr])
    }
    return oTag
}

var osvg = createTag('svg', {'xmlns':'svgNS', 'width':'800', 'height':'600'})
```

下面就是写4个生成函数了，其中圆、椭圆、矩形都有svg提供的标签，正六角星则需要我们通过path绘制

```javascript
function createCircle() {
    var circle = document.createElementNS('http://www.w3.org/2000/svg', 'circle')
    circle.setAttribute('cx', 70)
    circle.setAttribute('cy', 80)
    circle.r.baseVal.value = 70
    circle.setAttribute('fill', 'red')
    osvg.append(circle)
}

function createEllipse() {
    var ellipse = document.createElementNS('http://www.w3.org/2000/svg', 'ellipse')
    ellipse.setAttribute('cx', 70)
    ellipse.setAttribute('cy', 80)
    ellipse.setAttribute('rx', 70)
    ellipse.setAttribute('ry', 40)
    ellipse.setAttribute('fill', 'green')
    osvg.append(ellipse)
}

function createRectangle() {
    var rectangle = document.createElementNS('http://www.w3.org/2000/svg', 'rect')
    rectangle.setAttribute('cx', 70)
    rectangle.setAttribute('cy', 90)
    rectangle.setAttribute('width', 140)
    rectangle.setAttribute('height', 160)
    rectangle.setAttribute('fill', 'aqua')
    osvg.append(rectangle)
}

function createHexStar() {
    var hexagonalStar1 = document.createElementNS('http://www.w3.org/2000/svg', 'path')
    hexagonalStar1.setAttribute('d', 'm247.36202,313.63712l103.99999,-181.99998l103.99999,181.99998l-207.99998,0z')
    hexagonalStar1.setAttribute('fill', 'blue')
    var hexagonalStar2 = document.createElementNS('http://www.w3.org/2000/svg', 'path')
    hexagonalStar2.setAttribute('transform', 'rotate(-180 351.362 284.637)')
    hexagonalStar2.setAttribute('d', 'm247.36202,375.63712l103.99999,-181.99998l103.99999,181.99998l-207.99998,0z')
    hexagonalStar2.setAttribute('fill', 'blue')
    osvg.append(hexagonalStar1)
    osvg.append(hexagonalStar2)
}
```

最后在`handleSubmit()`中对输入的值进行判断从而执行不同的方法即可，执行前记得添加`document.getElementById('s').innerHTML = ""`来清空画布，下面是效果：

![GIF 2022-3-14 22-02-11](https://s2.loli.net/2022/03/14/3iXVdokKtZyr6En.gif)

最后放上代码：

```html
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>test</title>
</head>
<body>
    <input type="text" name="inp" id="inp">
    <button id="btn">确定</button>
    <div class="box"></div>

    <script>
        window.onload = function() {

            let svgNS = "http://www.w3.org/2000/svg"
            let div = document.querySelector('.box')

            function createTag(tag, obj) {
                var oTag = document.createElementNS(svgNS, tag)
                oTag.setAttribute('id', 's')
                for(var attr in obj) {
                    oTag.setAttribute(attr, obj[attr])
                }
                return oTag
            }

            var osvg = createTag('svg', {'xmlns':'svgNS', 'width':'800', 'height':'600'})

            function createCircle() {
                var circle = document.createElementNS('http://www.w3.org/2000/svg', 'circle')
                circle.setAttribute('cx', 70)
                circle.setAttribute('cy', 80)
                circle.r.baseVal.value = 70
                circle.setAttribute('fill', 'red')
                osvg.append(circle)
            }

            function createEllipse() {
                var ellipse = document.createElementNS('http://www.w3.org/2000/svg', 'ellipse')
                ellipse.setAttribute('cx', 70)
                ellipse.setAttribute('cy', 80)
                ellipse.setAttribute('rx', 70)
                ellipse.setAttribute('ry', 40)
                ellipse.setAttribute('fill', 'green')
                osvg.append(ellipse)
            }

            function createRectangle() {
                var rectangle = document.createElementNS('http://www.w3.org/2000/svg', 'rect')
                rectangle.setAttribute('cx', 70)
                rectangle.setAttribute('cy', 90)
                rectangle.setAttribute('width', 140)
                rectangle.setAttribute('height', 160)
                rectangle.setAttribute('fill', 'aqua')
                osvg.append(rectangle)
            }

            function createHexStar() {
                var hexagonalStar1 = document.createElementNS('http://www.w3.org/2000/svg', 'path')
                hexagonalStar1.setAttribute('d', 'm247.36202,313.63712l103.99999,-181.99998l103.99999,181.99998l-207.99998,0z')
                hexagonalStar1.setAttribute('fill', 'blue')
                var hexagonalStar2 = document.createElementNS('http://www.w3.org/2000/svg', 'path')
                hexagonalStar2.setAttribute('transform', 'rotate(-180 351.362 284.637)')
                hexagonalStar2.setAttribute('d', 'm247.36202,375.63712l103.99999,-181.99998l103.99999,181.99998l-207.99998,0z')
                hexagonalStar2.setAttribute('fill', 'blue')
                osvg.append(hexagonalStar1)
                osvg.append(hexagonalStar2)
            }

            function handleSubmit() {
                let input = document.getElementById('inp')
                let value = input.value

                document.getElementById('s').innerHTML = ""

                if(value==='C') {
                    createCircle()
                }

                if(value==='E') {
                    createEllipse()
                }

                if(value==='R') {
                    createRectangle()
                }

                if(value==='S') {
                    createHexStar()
                }
            }
            document.getElementById('btn').onclick = handleSubmit

            div.append(osvg)

        }
    </script>
</body>
</html>
```

JavaScript创建SVG

React学习02：React面向组件编程

<div style="text-align: center; width: 100%;">
    <img src="/static/img/d8bba1e02c433a08fd13dca0a119bfdd.logo.svg" alt="logo" style="width: 400px; margin: 50px auto; animation: App-logo-spin infinite 20s linear; background-color: transparent !important;" >
</div>



## React 简介

### 简介

官网

> - 英文官网：[React - A JavaScript library for building user interfaces](https://reactjs.org/)
> - 中文官网：[React官方中文文档 - 用于构建用户界面的 JavaScript 库](https://zh-hans.reactjs.org/)


介绍

> - 用于动态构建用户**界面**的js库（只关注于视图）
> - 由Facebook开源

### 特点

1. 声明式编码
2. 组件化编码
3. React Native 编写原生应用
4. 高效：DOM Diffing算法，最小化页面重绘

## Hello React 案例

### 引入js库

> 1. `react.development.js`：React核心库
> 2. `react-dom.development.js`：React操作DOM的扩展库
> 3. `babel.min.js`：解析JSX转为JS代码的库

### 完整代码

```jsx
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Hello React</title>
</head>
<body>
    <div id="test"></div>

    
    <script type="text/javascript" src="./js/react.development.js"></script>

    
    <script type="text/javascript" src="./js/react-dom.development.js"></script>

    
    <script type="text/javascript" src="./js/babel.min.js"></script>

    <script type="text/babel"> /* 此处必须为babel */

        // 1.创建虚拟DOM
        const VDOM = <h1>Hello React</h1> /*此处一定不要加引号，因为不是字符串*/

        // 2.渲染DOM
        ReactDOM.render(VDOM, document.getElementById('test'))
    </script>

</body>
</html>
```

### 效果展示

![image-20220212160103738](https://s2.loli.net/2022/02/12/i6GQzrBWXIt2J9O.png)

## 虚拟DOM与真实DOM

### 虚拟DOM

虚拟DOM本质就是js中的一个Object类型的对象（俗称一般对象），是React内部在用，无需太多属性。

```jsx
console.log('虚拟DOM', VDOM)
console.log(typeof VDOM)
console.log(VDOM instanceof Object)
```

![image-20220212191213683](https://s2.loli.net/2022/02/12/e79P8E3UudfczCm.png)

### 真实DOM

真实DOM包含众多属性，虚拟DOM最终会被React转化为真实DOM，呈现在页面上。

```jsx
const TDOM = document.getElementById('test')
console.log('真实DOM', TDOM)
debugger;
```

![image-20220212191714751](https://s2.loli.net/2022/02/12/rElCs5AxqkeZJLY.png)

### 虚拟DOM的两种创建方式

1. 使用jsx创建虚拟DOM（jsx的语法糖）

   ```jsx
   const VDOM = <h1 id="title">Hello React</h1>
   ReactDOM.render(VDOM, document.getElementById('test'))
   ```

   嵌套标签

   ```jsx
   const VDOM = (
       <h1 id="title">
           <span>Hello React</span>
       </h1>
   )
   ReactDOM.render(VDOM, document.getElementById('test'))
   ```

2. 使用js创建虚拟DOM（不推荐）

   ```jsx
   const VDOM = React.createElement('h1', {id:'title', class:'t'}, 'Hello React')
   ReactDOM.render(VDOM, document.getElementById('test'))
   ```

   嵌套标签

   ```jsx
   const VDOM = React.createElement('h1', {id:'title', class:'t'}, React.createElement('span', {}, 'Hello React'))
   ReactDOM.render(VDOM, document.getElementById('test'))
   ```

## JSX语法规则

### JSX

JSX全称`JavaScript XML`，是React定义的一种类似于XML的JS扩展语法，其本质是`React.createElement(component, props, ...children)`方法的语法糖。

> 存储和传输数据：
>
> XML
>
> ```xml
> <student>
>     <name>Morales</name>
>     <age>22</age>
> </student>
> ```
>
> JSON
> JS内置JSON对象，JSON.parse()和JSON.stringify()
>
> ```json
> "{"name":"Morales","age":22}"
> ```

JSX的作用：用来简化创建虚拟DOM

> 1. 写法：`var ele = <h1>Hello JSX</h1>`
> 2. 既不是字符串也不是`HTML/XML`标签
> 3. 最终产生JS对象

### 语法规则

1. 定义虚拟DOM时，不要写引号；

   ```jsx
   const VDOM = <h1>Hello React</h1>
   ```

2. 标签中混入JS表达式时要用`{}`；

   ```jsx
   const myId = 'morales'
   const myData = 'Hello REact'
   const VDOM = (
       <h2 id={myId}>
           <span>{myData.toLowerCase()}</span>
       </h2>
   )
   ```

   ![image-20220212194154463](https://s2.loli.net/2022/02/12/SQ5Iw9kXe4cHyE7.png)

3. 样式的类名指定不要用`class`（`class`是`ES6`定义的关键字），要用`className`；

   ```css
   .title {
       background-color: aqua;
       width: 500px;
   }
   ```

   ```jsx
   const VDOM = (
       <h2 id={myId} className="title">
           <span>{myData.toLowerCase()}</span>
       </h2>
   )
   ```

   ![image-20220212194048130](https://s2.loli.net/2022/02/12/KYOhTSHm2ZNLw67.png)

4. 内联样式，要用`style={{key:value}}`的形式写；

   ```jsx
   <span style={{color:'orange', fontSize:'50px'}}>{myData.toLowerCase()}</span>
   ```

   ![image-20220212195047562](https://s2.loli.net/2022/02/12/zHBCDmKSlgLfpnt.png)

5. 虚拟DOM必须只能有一个根标签；

   ```jsx
   const VDOM = (
       <div>
           <h2 id={myId} className="title">
               <span style={{color:'orange', fontSize:'50px'}}>{myData.toLowerCase()}</span>
           </h2>
           <h2 id={myId.toUpperCase()} className="title">
               <span style={{color:'orange', fontSize:'50px'}}>{myData.toLowerCase()}</span>
           </h2>
       </div>
   )
   ```

6. 标签必须闭合；

   ```jsx
   <input type="text" />
   ```

7. 标签首字母：

   > 1. 若小写字母开头，则将该标签转为html中同名标签，若html无同名标签，则报错；
   >    ![image-20220212200550241](https://s2.loli.net/2022/02/12/qgL2dziWH4NG1su.png)
   > 2. 若大写字母开头，则React将渲染对应的组件，若组件未定义，则报错。
   >    ![image-20220212200738415](https://s2.loli.net/2022/02/12/s2vbHYoLVrOdQRy.png)

## JSX练习

### 效果

![image-20220212203558145](https://s2.loli.net/2022/02/12/YoilZ2VT6M5zAQK.png)

### 完整代码

```jsx
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>JSX练习</title>
</head>
<body>
    <div id="test"></div>

    
    <script type="text/javascript" src="./js/react.development.js"></script>

    
    <script type="text/javascript" src="./js/react-dom.development.js"></script>

    
    <script type="text/javascript" src="./js/babel.min.js"></script>

    <script type="text/babel"> /* 此处必须为babel */

        // 模拟数据
        const data = ['Angular', 'React', 'Vue']

        // 1.创建虚拟DOM
        const VDOM = (
            <div>
                <h1>前端js框架列表</h1>
                <ul>
                    { // 此处仅可以写js表达式
                        
                        /*此写法以后可能会产生严重问题，入门阶段为方便学习暂时使用此写法*/
                        data.map((item,index)=>{
                            return <li key={index}>{item}</li>
                        })
                    }
                </ul>
            </div>
        )
        // 2.渲染虚拟DOM到页面
        ReactDOM.render(VDOM, document.getElementById('test'))

    </script>

</body>
</html>
```

![image-20220212203014878](https://s2.loli.net/2022/02/12/BhmTXiRqSgNweHZ.png)

## 模块与组件

### 模块

模块是向外提供特定功能的js程序，一般就是一个js文件

随着业务逻辑增加，代码越来越多且复杂，因此使用模块

作用：复用js，简化js的编写，提高js运行效率

### 组件

组件是用来实现局部功能效果的代码和资源的集合（html/css/js/image等）

一个界面的功能更复杂时用到组件

作用：复用编码，简化项目编码，提高运行效率

### 模块化

当应用的js都以模块来编写时，这个应用就是一个模块化的应用

### 组件化

当应用是以多组件的方式实现时，这个应用就是一个组件化的应用

React学习01：React入门

> 给定两个字符串A和B，请判断B是否是A的子串。
> 如果是，返回B在A中第一次出现的位置；
> 如果不是，返回-1。





什么意思呢？我们来举一个例子：

> 字符串A： a b b c e f g h 
> 字符串B： b c e

字符串B是A的子串，B第一次在A中出现的位置下标是2，所以返回 **2**。

> 字符串A： a b c d e f g h 
> 字符串B： a d e g

字符串B在A中并不存在，所以返回 **-1**。

为了统一概念，在后文中，我们把字符串A称为**主串**，把字符串B称为**模式串**。

------



## BF算法

Brute Force（暴力算法）的缩写。

### 分析

直接从头开始，把主串和模式串的字符逐个进行匹配，如果发现不匹配，再从主串下一位开始，比较简单粗暴。

**第一轮**，从主串的第0位开始，把主串和模式串的字符逐个比较：

![image.png](/static/img/1e534b0db669950f595ec51aa97ecdd4.image.png)

显然两者并不匹配。

**第二轮**，把模式串后移一位，从主串的第1位开始，把主串和模式串的字符逐个比较：

![image.png](/static/img/afe9f27b45d98453dfff89e9744513cb.image.png)

主串的第1位字符是b，模式串的第1位字符也是b，两者匹配，继续比较：

![image.png](/static/img/321b1db52714ac3f3af8d9e48444124c.image.png)

主串的第2位字符是b，模式串的第2位字符是c，两者并不匹配。

**第三轮**，把模式串再次后移一位，从主串的第2位开始，把主串和模式串的字符逐个比较：

![image.png](/static/img/b83179a700df634efd086462a49fccb9.image.png)

主串的第2位字符是b，模式串的第2位字符也是b，两者匹配，继续比较：

![image.png](/static/img/4171da48cf3485fd4eb1fd7729db6056.image.png)

主串的第3位字符是c，模式串的第3位字符也是c，两者匹配，继续比较：

![image.png](/static/img/e61d363164e2ca2fd1e30370871c58e0.image.png)

主串的第4位字符是e，模式串的第4位字符也是e，两者匹配，比较完成。

由此得到结果，模式串 bce 是主串 abbcefgh 的子串，在主串第一次出现的位置下标是 2：

![image.png](/static/img/5ae832603c0feac78bc1b454a33794ca.image.png)

### 代码实现

```c++
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s1 = "abbcefgh";
    string s2 = "bce";
    //cin>>s1>>s2;
    int n1=s1.size(), n2=s2.size();
    int i=0, j=0;
    int flag = 0;
    while(i<n1 && j<n2)
    {
        if(s1[i]==s2[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i-j+1;
            j = 0;
        }
        if(j==n2)
        {
            cout<<i-n2<<endl;
            break;
        }
    }
    return 0;
}
```

### 效率

字符逐个比较，在某些极端情况下效率极低，例如：

> 主串： dddddddddddddn
> 模式串： dddn

假设主串的长度是m，模式串的长度是n，那么在这种极端情况下，BF算法的最坏时间复杂度是`O(mn)`。



## RK算法

全称Rabin-Karp算法，以其发明者Rabin和Karp的名字命名。

### 分析

RK算法比较的是两个字符串的哈希值。

每一个字符串都可以通过某种哈希算法，转换成一个整型数，这个整型数就是hashcode：hashcode = hash(string)

显而易见，相对于逐个字符比较两个字符串，仅比较两个字符串的hashcode要容易得多。

**第一步，需要生成模式串的hashcode。**

生成hashcode的算法多种多样，比如：

- **按位相加**
  这是最简单的方法，我们可以把a当做1，b当做2，c当做3......然后把字符串的所有字符相加，相加结果就是它的hashcode。
  bce =  2 + 3 + 5 = 10
  但是，这个算法虽然简单，却很可能产生hash冲突，比如bce、bec、cbe的hashcode是一样的。
- **转换成26进制数**
  既然字符串只包含26个小写字母，那么我们可以把每一个字符串当成一个26进制数来计算。
  bce = 2*(26^2) + 3*26 + 5 = 1435
  这样做的好处是大幅减少了hash冲突，缺点是计算量较大，而且有可能出现超出整型范围的情况，需要对计算结果进行取模。

 为了方便演示，此处采用按位相加的hash算法，所以bce的hashcode是10：

![image.png](/static/img/3a667717895fd46236a0eaa5d9f56630.image.png)

**第二步，生成主串当中第一个等长子串的hashcode。**

由于主串通常要长于模式串，把整个主串转化成hashcode是没有意义的，只有比较主串当中**和模式串等长的子串**才有意义。

因此，我们首先生成主串中第一个和模式串等长的子串hashcode，即abb = 1 + 2 + 2 = 5：

![image.png](/static/img/9fcf0911c5c5dc5e874610b82dafde36.image.png)
**第三步，比较两个hashcode。**

显然5 != 10，说明模式串和第一个子串不匹配，继续下一轮比较。

**第四步，生成主串当中第二个等长子串的hashcode。**

bbc = 2 + 2 + 3 = 7：

![image.png](/static/img/dc0bc42b13d61c1277d6bdc17e9cb243.image.png)

**第五步，比较两个hashcode。**

显然7!=10，说明模式串和第二个子串不匹配，继续下一轮比较。

**第六步，生成主串当中第三个等长子串的hashcode。**

bce= 2 + 3 + 5 = 10：

![image.png](/static/img/2fbbf41a23e6a4fbac01ee3f3105ed5f.image.png)

**第七步，比较两个hashcode。**

显然10==10，两个hashcode相等。

第八步，逐个字符比较两字符串。

hashcode的比较只是初步验证，之后我们还需要像BF算法那样，对两个字符串逐个字符比较，最终判断出两个字符串匹配。

最后得出结论，模式串bce是主串abbcefgh的子串，第一次出现的下标是2：

![image.png](/static/img/40d42695111188a3c5c353b1f6fa7c1b.image.png)

### 代码实现

```c++
#include<bits/stdc++.h>
using namespace std;
int Hash(string str) // 计算hashcode 
{
    int hashcode = 0;
    for(int i=0; i<str.size(); i++)
        hashcode += str[i]-'a'; // 以按位相加方法 
    return hashcode;
}
bool comp(int index, string s1, string s2) // 进行精确比较
{
    if(s1.compare(index, s2.size(), s2) == 0) return 1;
    //if(s1.substr(index, s2.size()) == s2) return 1;  皆可
    else return 0; 
}
int RK(string str1, string str2)
{
    int n1=str1.size(), n2=str2.size();
    int code1 = Hash(str1.substr(0, n2));
    int code2 = Hash(str2);
    for(int i=0; i<n1-n2+1; i++)
    {
        //cout<<code1<<" "<<code2<<endl;
        if(code1==code2 && comp(i, str1, str2)) return i;
        // 判断是否已进行到最后一轮 
        if(i < n1-n2) // 若非最后一轮
        {
            code1 -= str1[i]-'a';
            code1 += str1[i+n2]-'a';
        } // 更新hash值
    }
    return -1; // 若非子串则返回-1
}
int main()
{
    string s1 = "abbcefgh";
    string s2 = "bce";
    cout<<RK(s1, s2)<<endl; // 输出第一次出现的下标 
    return 0;
}
```

### 效率

RK算法计算单个字串hash的时间复杂度是O(n)，且由于后续字串的hash为增量计算，时间复杂度仍为`O(n)`。

RK算法的缺点在于哈希冲突，每次冲突产生时，RK算法都要对子串和模式串进行逐个字符比较，当冲突过多时，RK算法就**退化**为BF算法了。

## KMP算法

全称Knuth-Morris-Pratt算法，由D.E.Knuth，J.H.Morris，V.R.Pratt研究而得。又名“看猫片”算法。

### 分析

假设现在主串A匹配到 i 位置，模式串B匹配到 j 位置：

- 如果`j == -1`，或者当前字符匹配成功（即`A[i] == B[j]`），则令`i++`，`j++`，继续匹配下一个字符；
- 如果`j != -1`，且当前字符匹配失败（即`A[i] != B[j]`），则令 `i` 不变，`j = next[j]`。这种操作意味着失配（不匹配）时，模式串相对于主串向右移动了`j - next [j]` 位。

当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值，即 **移动的实际位数为：`j - next[j]`**，且此值大于等于1。

**第一步，主串逐位与模式串第0位比较，直至二者匹配。**

a与b不匹配，j=0，i++，此时b与b匹配。

![image.png](/static/img/65284a20c897415d7a4d6fd4e03ff42d.image.png)

**第二步，两串指针均后移一位，进行比较。**

i++，j++，此时j=1，且b与c不匹配。

![image.png](/static/img/ee46871713bdc5f26356fcac673f8ac8.image.png)

当模式串中j 处的字符失配时，下一步用next[j]处的字符继续跟主串匹配，相当于模式串向右移动`j - next[j]` 位。 

**第三步，i不变，j回溯。**

模式串相对于主串移动了`j-next[j]`位。

![image.png](/static/img/49b5d5ebf0bdd68485bf7a9259bf59f8.image.png)

此时b==b，匹配。

**第四步，两串指针均后移一位，进行比较。**

匹配完成。

![image.png](/static/img/2e9ec17e3ae18202e6003769d63b7329.image.png)

[阮一峰的思路讲解](http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html)

### next数组

next数组与“部分匹配表”（储存“部分匹配值”的表）有关。“部分匹配值”是"前缀"和"后缀"的最长的共有元素的长度。

- "前缀"：除了最后一个字符以外，一个字符串的全部头部组合；
- "后缀"：除了第一个字符以外，一个字符串的全部尾部组合。

以字符串ABCDABD为例：

![image.png](/static/img/4939a3fba14353fa1d0653b8679aa358.image.png)

据此表可得结论：**失配时，模式串向右移动的位数 = 已匹配*字符数* - 失配字符的上一位字符所对应的部分匹配值**。

当匹配到一个字符失配时，我们看到的是失配字符的上一位字符对应的部分匹配值。如此，便有next 数组：

|            |  A   |  B   |  C   |  D   |  A   |  B   |  D   |
| :--------: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
| 部分匹配值 |  0   |  0   |  0   |  0   |  1   |  2   |  0   |
| next数组值 |  -1  |  0   |  0   |  0   |  0   |  1   |  2   |

据此next数组，得到：**失配时，模式串向右移动的位数 = 失配字符*所在位置* - 失配字符对应的next 值**。

计算next 数组可以采用递推的方法。

> 对于P的前j+1个序列字符：
>
> - 若`p[k] == p[j]`，则`next[j + 1 ] = next [j] + 1 = k + 1`；
> - 若`p[k] ≠ p[j]`，如果此时`p[ next[k] ] == p[j ]`，则`next[ j + 1 ] =  next[k] + 1`，否则继续递归前缀索引`k = next[k]`，而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"`p0 p1, …, pk-1 pk`"跟后缀"`pj-k pj-k+1, …, pj-1 pj`"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “`p0 p1, …, pt-1 pt`” 等于长度更小的后缀 “`pj-t pj-t+1, …, pj-1 pj`” 呢？如果存在，那么这个`t+1` 便是`next[ j+1]`的值，此相当于利用已经求得的next 数组（`next [0, ..., k, ..., j]`）进行P串前缀跟P串后缀的匹配。

[详细计算方法参考](https://blog.csdn.net/v_july_v/article/details/7041827)

### 代码实现

```c++
#include<bits/stdc++.h>
using namespace std;
int Next[10];
void getNEXT(string str)
{
    Next[0] = -1;
    int i=-1, j=0;
    while(j < str.size()-1)
    { // str[i]表示前缀，str[j]表示后缀 
        if(i==-1 || str[j]==str[i])
        {
            i++;
            j++;
            Next[j] = i;
            if(str[j] != str[i]) Next[j] = i;
            else Next[j] = Next[i];
        }
        else i = Next[i];
    }
}
int KMP(string str1, string str2)
{
    int i=0, j=0; // 两串的指针
    int len1=str1.size(), len2=str2.size();
    while(i<len1 && j<len2)
    {
        if(j==-1 || str1[i]==str2[j])
        {
            i++;
            j++;
        }
        else j = Next[j];
    }
    if(j == len2)
        return i-j;
    else return -1;
}
int main()
{
    string s1 = "abbcefgh";
    string s2 = "bce";
    getNEXT(s2);
    cout<<KMP(s1, s2)<<endl;
    return 0;
}
```

> 1. 匹配失败时，总是能够让 pattern 回退到某个位置，使 text 不用回退。
> 2. 在字符串比较时，pattern 提供的信息越多，计算复杂度越低。

### 效率

如果某个字符匹配成功，模式串首字符的位置保持不动，仅仅是i++、j++；如果匹配失配，i 不变（即 i 不回溯），模式串会跳过匹配过的`next [j]`个字符。整个算法最坏的情况是，当模式串首字符位于i - j的位置时才匹配成功，算法结束。

所以，如果主串的长度为n，模式串的长度为m，那么匹配过程的时间复杂度为O(n)，算上计算next的O(m)时间，KMP的整体时间复杂度稳定在`O(m + n)`。

## Sunday算法

是Daniel M.Sunday于1990年提出的一种字符串模式匹配算法。

### 分析

Sunday算法的核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配。

我们对模式串做一个简单而巧妙的预处理：记录模式串中**每一种字符最后出现的位置**，将其存入一个数组中。

|  b   |  c   |  e   |
| :--: | :--: | :--: |
|  0   |  1   |  2   |

我们假定主串名为str，长度为n；模式串名为pattern，长度为m。

若在发生不匹配时`str[i]≠pattern[j]，0≤i<n，0≤j<n`。设`str`此次第一个匹配的字符位置为L。显然，`str[L+m]`肯定要参加下一轮的匹配，并且`pattern`至少要与`str[L+m]`匹配才有可能与整个str匹配。

![此时不匹配，i=0，j=0，L=1](/static/img/6e8e63c36d2d2c33ed3391e6e791143f.image.png)

这时就可以寻找`pattern`中`str[L+m]`出现的位置了。利用我们预处理好的数组，可以`O(1)`查找出该位置K，并将其直接移动至`pattern[K]==str[L+m]`。特殊地，**若`str[L+m]`没有在`pattern`中出现，那么`pattern`不可能会与`str[L+m]`匹配**，则将`pattern`的第一位直接移动到`str[L+m+1]`，继续匹配。直至`L+m > n`时，匹配完毕。

![str[L+m]=='e'，pattern[K]=='e'](/static/img/ff89aa5e6193aa7e4c7f634080c2b6b0.image.png)

```c++
#include<bits/stdc++.h>
using namespace std;
int Lpos[256]; // 记录模式串中每一种字符最后出现的位置
int str, pattern;
void mem(string s)
{
    memset(Lpos, -1, sizeof(Lpos));
    for(int i=0; i<=pattern; i++)
        Lpos[s[i]] = i;
}
int Sunday(string str1, string str2)
{
    int L=0;
    while(L+pattern <= str)
    {
        int i=0;
        bool flag=1;
        while(i<=pattern && flag)
        {
            if(str1[L+i] != str2[i]) flag=0;
            i++;
        }
        if(flag)
            return L;
        else
        {
            i = pattern+1;
            if(Lpos[str1[L+i]] == -1) L += i+1;
            else L += i-Lpos[str1[L+i]];
        }
    }
    return -1;
}
int main()
{
    string s1 = "abbcefgh";
    string s2 = "bce";
    str = s1.size()-1;
    pattern = s2.size()-1;
    mem(s2);
    cout<<Sunday(s1, s2)<<endl;
    return 0;
}
```

### 效率

平均性能的时间复杂度为`O(n)`，最差情况的时间复杂度为`O(nm)`。

Sunday算法的扫描顺序是没有限制的。为了提高在最坏情况下的算法效率，可以对模式串中的字符按照其出现的概率从小到大的顺序扫描，这样能尽早地确定失配与否。

------

## 相关题目

NEFU OJ：

- [275 - ](http://acm.nefu.edu.cn/problemShow.php?problem_id=275)[搜索字符串](http://acm.nefu.edu.cn/problemShow.php?problem_id=275) 
- [1351 - 子串匹配 ](http://acm.nefu.edu.cn/problemShow.php?problem_id=1351)
- [2104 - 查找子串](http://acm.nefu.edu.cn/problemShow.php?problem_id=2104)

HDU：

- [2087 - 剪花布条](http://acm.hdu.edu.cn/showproblem.php?pid=2087)

React 开发者工具