STM32MP157（二）——U-Boot移植

STM32MP157（一）——TF-A移植

# 半加器

![半加器](https://qncdn.oleehu.xyz/blog/SystemC/%E5%8D%8A%E5%8A%A0%E5%99%A8.drawio.svg)




```c++
//文件：half_adder.h

#pragma once
#include <systemc>
using namespace sc_core;

/*
 * @brief 半加器模块
 * 
 * 该模块实现了一个基本的半加器功能，接收两个输入位并产生一个和位和一个进位输出。
 * 
 * @param a 输入位a
 * @param b 输入位b
 * @param sum 输出的和位
 * @param carry 输出的进位
 */
SC_MODULE(half_adder){
    sc_in <bool> a,b; // 输入端口
    sc_out<bool>sum,carry; // 输出端口

    /*
     * @brief 半加器的处理函数
     * 
     * 该函数负责计算输入位a和b的和以及产生的进位。
     */
    void prc_half_adder();

    /*
     * @brief 半加器的构造函数
     * 
     * 初始化半加器模块，将prc_half_adder函数注册为响应函数，当输入a或b发生变化时触发。
     */
    SC_CTOR(half_adder){
        SC_METHOD(prc_half_adder);
        sensitive << a << b;
    }

};

//文件：half_adder.cpp

#include "half_adder.h"
/**
 * @brief 实现半加器逻辑
 * 
 * 该函数不接受参数，也不返回值，但会修改类内的sum和carry成员变量。
 * 它完成两个二进制位a和b的加法操作，计算出它们的和(sum)以及进位(carry)。
 */
void half_adder::prc_half_adder() {
    // 计算a和b的异或结果，得到无进位相加的和
    sum=a^b;
    // 计算a和b的与结果，得到产生的进位
    carry=a&b;
}

```

# 全加器

![全加器](https://qncdn.oleehu.xyz/blog/SystemC/%E5%85%A8%E5%8A%A0%E5%99%A8.svg)


```c++
//文件：full_adder.h

#pragma once
#include "half_adder.h"
using namespace sc_core;

/*
 * 全加器模块
 * 该模块实现了一个基本的全加器功能，可以对两个输入位a、b以及一个进位输入carry_in进行加法操作，
 * 并产生一个和输出sum以及一个进位输出carry_out。
 */
SC_MODULE(full_adder){
    sc_in<bool>a, b, carry_in; // 输入端口：a、b为两个待加位，carry_in为进位输入
    sc_out<bool>sum, carry_out; // 输出端口：sum为加法结果的和，carry_out为产生的进位输出

    sc_signal<bool>c1, c2, s1; // 中间信号量，用于内部计算过程
    void prc_or(); // 处理或逻辑的过程函数
    half_adder *ha1_ptr, *ha2_ptr; // 指向half_adder实例的指针

    /**
     * 全加器构造函数
     * 用于初始化全加器模块，创建两个half_adder实例并连接它们以实现全加器功能。
     */
    SC_CTOR(full_adder){
        ha1_ptr = new half_adder("ha1"); // 创建第一个half_adder实例
        // 命名关联第一个half_adder的输入和输出
        ha1_ptr->a(a);
        ha1_ptr->b(b);
        ha1_ptr->sum(s1);
        ha1_ptr->carry(c1);
        
        ha2_ptr = new half_adder("ha2"); // 创建第二个half_adder实例
        // 位置关联第二个half_adder的输入和输出
        (*ha2_ptr)(s1, carry_in, sum, c2);
        
        SC_METHOD(prc_or); // 注册方法prc_or，用于处理或逻辑
        sensitive << c1 << c2; // 指定prc_or方法对c1和c2信号敏感
        
    }
    // 析构函数
    ~full_adder(){
        delete ha1_ptr; // 删除第一个half_adder实例
        delete ha2_ptr; // 删除第二个half_adder实例
    }
};

//文件：full_adder.cpp

#include "full_adder.h"

/**
 * full_adder::prc_or 函数实现或门逻辑处理
 * 本函数用于处理全加器中的或门逻辑，即计算两个进位输入c1和c2的或运算结果，
 * 并将结果作为carry_out的值。
 * 
 * 参数:
 * c1 -- 第一个进位输入
 * c2 -- 第二个进位输入
 * 
 * 返回值:
 * 无返回值，但会将c1和c2的或运算结果存储在carry_out成员变量中。
 */
void full_adder::prc_or() {
  // 计算c1和c2的或运算结果，并将结果存储在carry_out中
  carry_out=c1|c2;
  }

```
# 验证功能


```c++
//文件：driver.h

#pragma once
#include<systemc>
using namespace sc_core;
/*
 * @brief driver模块，用于提供驱动逻辑。
 * 
 * 该模块包含三个输出信号：d_a, d_b, d_cin，并通过prc_driver过程来控制这些信号的逻辑行为。
 */
SC_MODULE(driver){
    // 输出信号声明
	sc_out<bool>d_a, d_b, d_cin;

    /**
     * @brief prc_driver过程，模块的主要逻辑过程。
     * 
     * 该过程为线程，用于控制和驱动输出信号d_a, d_b, d_cin的行为。
     */
	void prc_driver();
	
    /**
     * @brief driver模块的构造函数。
     * 
     * 通过构造函数初始化模块，创建并启动prc_driver过程。
     */
	SC_CTOR(driver){
		SC_THREAD(prc_driver); // 创建并启动一个线程过程prc_driver
	}
	
};

//文件：driver.cPP

#include "driver.h"

/**
 * @brief driver类的prc_driver成员函数
 * 
 * 该函数是一个无限循环，主要功能是周期性地更新d_a, d_b, d_cin的值，并等待一定时间。
 * 它没有参数和返回值。
 */
void driver::prc_driver() {
	sc_dt::sc_uint<3> pattern;  // 定义一个3位的整型变量pattern，用于存储当前的模式值
	pattern=0;           // 初始化pattern为0
	while (1)            // 进入一个无限循环
	{
		d_a=pattern[0];   // 将pattern的最低位赋值给d_a
		d_b=pattern[1];   // 将pattern的第二位赋值给d_b
		d_cin=pattern[2]; // 将pattern的最高位赋值给d_cin
		wait(5,SC_NS);    // 等待5纳秒
		pattern++;         // 将pattern的值加1，为下一次循环准备
	}
	
}

//文件：monitor.h

#pragma once
#include <systemc>
using namespace sc_core;

/**
 * @brief 监视器模块，用于监视多个信号的状态变化。
 *
 * 该模块连接了五个信号：m_a, m_b, m_cin, m_sum, m_cout。
 * 当这些信号中的任何一个发生变化时，都会触发prc_monitor方法。
 */
SC_MODULE(monitor){
    sc_in<bool> m_a, m_b, m_cin, m_sum, m_cout; // 输入信号声明

    /**
     * @brief 监视器的处理函数。
     *
     * 当监视的信号发生变化时被调用，用于执行相应的监视逻辑。
     */
    void prc_monitor();

    /**
     * @brief 监视器的构造函数。
     *
     * 初始化监视器模块，设置当哪些信号变化时触发prc_monitor方法。
     */
    SC_CTOR(monitor){
        SC_METHOD(prc_monitor); // 方法声明，当指定的信号变化时执行prc_monitor
        sensitive << m_a << m_b << m_cin << m_sum << m_cout; // 指定敏感信号
    }
    
};

//文件：monitor.cpp

#include "monitor.h"

/**
 * @brief 实现监控器的处理函数
 * 该函数用于监控并打印当前时间以及变量a、b、carry_in、sum、carry_out的值。
 * 
 */
void monitor::prc_monitor() {
    // 打印当前时间及传入参数和内部状态的值
    std::cout<<"At time"<<sc_time_stamp()<<"::";
	std::cout<<"(a,b,carry_in):";
	std::cout<<m_a<<m_b<<m_cin;
	std::cout<<"(sum,carry_out):"<<m_sum<<m_cout<<std::endl;

}

//文件：full_adder_main.cpp

#include"driver.h"
#include"monitor.h"
#include"full_adder.h"

/**
 * @brief 主函数，用于演示如何使用SCampilkan库实现一个全加器，并通过波形驱动和监控进行验证。
 * 
 * @param argc 参数个数。
 * @param argv 参数值数组。
 * @return int 总是返回0，表示成功执行。
 */
int sc_main(int argc, char* argv[]) {
    // 定义全加器的输入和输出信号
	sc_signal<bool> t_a,t_b,t_cin,t_sum,t_cout;

    // 实例化一个全加器模块和一个波形驱动模块
	full_adder f1("FullAdderWithHalfAdder");
	driver d1("GenerateWaveforms");

    // 使用位置关联方式连接全加器模块
	f1<<t_a<<t_b<<t_cin<<t_sum<<t_cout;

    // 使用命名关联方式连接波形驱动模块
	d1.d_a(t_a);
	d1.d_b(t_b);
	d1.d_cin(t_cin);

    // 实例化一个波形监控模块并使用位置关联方式连接
	monitor mo1("MonitorWaveforms");
	mo1<<t_a<<t_b<<t_cin<<t_sum<<t_cout;

    // 启动SCimulation，设置模拟时间为100ns
	sc_start(100,SC_NS);
	
    // 程序执行结束，返回0
	return(0);

}
```

# 结果

```
        SystemC 2.3.3-Accellera --- Oct  4 2020 22:59:38
        Copyright (c) 1996-2018 by all Contributors,
        ALL RIGHTS RESERVED

Info: (I804) /IEEE_Std_1666/deprecated: positional binding using << or , is deprecated, use () instead.
At time0 s::(a,b,carry_in):000(sum,carry_out):00
At time5 ns::(a,b,carry_in):100(sum,carry_out):00
At time5 ns::(a,b,carry_in):100(sum,carry_out):10
At time10 ns::(a,b,carry_in):010(sum,carry_out):10
At time15 ns::(a,b,carry_in):110(sum,carry_out):10
At time15 ns::(a,b,carry_in):110(sum,carry_out):01
At time20 ns::(a,b,carry_in):001(sum,carry_out):01
At time20 ns::(a,b,carry_in):001(sum,carry_out):11
At time20 ns::(a,b,carry_in):001(sum,carry_out):10
At time25 ns::(a,b,carry_in):101(sum,carry_out):10
At time25 ns::(a,b,carry_in):101(sum,carry_out):00
At time25 ns::(a,b,carry_in):101(sum,carry_out):01
At time30 ns::(a,b,carry_in):011(sum,carry_out):01
At time35 ns::(a,b,carry_in):111(sum,carry_out):01
At time35 ns::(a,b,carry_in):111(sum,carry_out):11
At time40 ns::(a,b,carry_in):000(sum,carry_out):11
At time40 ns::(a,b,carry_in):000(sum,carry_out):01
At time40 ns::(a,b,carry_in):000(sum,carry_out):00
At time45 ns::(a,b,carry_in):100(sum,carry_out):00
At time45 ns::(a,b,carry_in):100(sum,carry_out):10
At time50 ns::(a,b,carry_in):010(sum,carry_out):10
At time55 ns::(a,b,carry_in):110(sum,carry_out):10
At time55 ns::(a,b,carry_in):110(sum,carry_out):01
At time60 ns::(a,b,carry_in):001(sum,carry_out):01
At time60 ns::(a,b,carry_in):001(sum,carry_out):11
At time60 ns::(a,b,carry_in):001(sum,carry_out):10
At time65 ns::(a,b,carry_in):101(sum,carry_out):10
At time65 ns::(a,b,carry_in):101(sum,carry_out):00
At time65 ns::(a,b,carry_in):101(sum,carry_out):01
At time70 ns::(a,b,carry_in):011(sum,carry_out):01
At time75 ns::(a,b,carry_in):111(sum,carry_out):01
At time75 ns::(a,b,carry_in):111(sum,carry_out):11
At time80 ns::(a,b,carry_in):000(sum,carry_out):11
At time80 ns::(a,b,carry_in):000(sum,carry_out):01
At time80 ns::(a,b,carry_in):000(sum,carry_out):00
At time85 ns::(a,b,carry_in):100(sum,carry_out):00
At time85 ns::(a,b,carry_in):100(sum,carry_out):10
At time90 ns::(a,b,carry_in):010(sum,carry_out):10
At time95 ns::(a,b,carry_in):110(sum,carry_out):10
At time95 ns::(a,b,carry_in):110(sum,carry_out):01
```

SystemC实战（一）——全加器

# 找出字符串中第一个匹配项的下标
给你两个字符串 `haystack` 和 `needle` ，请你在 `haystack` 字符串中找出 `needle` 字符串的第一个匹配项的下标（下标从 `0` 开始）。如果 `needle` 不是 `haystack` 的一部分，则返回  `-1` 。

 

示例 1：

输入：`haystack = "sadbutsad", needle = "sad"`

输出：`0`
解释："`sad`" 在下标 `0` 和 `6` 处匹配。

第一个匹配项的下标是 `0` ，所以返回 `0`。

示例 2：

输入：`haystack = "leetcode", needle = "leeto`"

输出：`-1`

解释："`leeto`" 没有在 "`leetcode`" 中出现，所以返回 `-1` 。
 



提示：

`1 <= haystack.length, needle.length <= 104`

`haystack` 和 `needle` 仅由小写英文字符组成

![找出字符串中第一个匹配项的下标](https://qncdn.oleehu.xyz/blog/LeetCode/%E6%89%BE%E5%87%BA%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%8C%B9%E9%85%8D%E9%A1%B9%E7%9A%84%E4%B8%8B%E6%A0%87.png)


```c++
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(haystack.length()<needle.length()){
            return -1;
        }
        for(int i=0;i<=haystack.length()-needle.length();i++){
            for(int j=0;j<needle.length();){
                if(needle[j]==haystack[i+j]){
                    
                    j++;
                }
                else{
                    
                    j=0;
                    break;
                }
                if(j==needle.length()){
                    return i;
                }
            }
        }
            return -1;
    }
};
```
空间复杂度：$O(1)$

使用了常数级别的额外空间，没有使用额外的数据结构来存储信息。

时间复杂度：$O((n-m+1)*m)$

其中，$n$是$haystack$的长度，$m$是$needle$的长度。算法的时间复杂度主要取决于两个嵌套的循环。外层循环最多执行$n-m+1$次，内层循环最多执行$m$次。因此，总的时间复杂度为$O((n-m+1)*m)$。

# 题解一：暴力匹配

作者：力扣官方题解

链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/732236/shi-xian-strstr-by-leetcode-solution-ds6y/

来源：力扣（LeetCode）

思路及算法

我们可以让字符串 $needle$ 与字符串 $haystack$ 的所有长度为 $m$ 的子串均匹配一次。

为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 $−1$。

![找出字符串中第一个匹配项的下标(题解一）](https://qncdn.oleehu.xyz/blog/LeetCode/%E6%89%BE%E5%87%BA%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%8C%B9%E9%85%8D%E9%A1%B9%E7%9A%84%E4%B8%8B%E6%A0%87%28%E9%A2%98%E8%A7%A3%E4%B8%80%29.png)

```c++
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        for (int i = 0; i + m <= n; i++) {
            bool flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack[i + j] != needle[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
};
```
复杂度分析

时间复杂度：$O(n×m)$，其中 $n$ 是字符串 $haystack$ 的长度，$m$ 是字符串 $needle$ 的长度。最坏情况下我们需要将字符串 $needle$ 与字符串 $haystack$ 的所有长度为 $m$ 的子串均匹配一次。

空间复杂度：$O(1)$。我们只需要常数的空间保存若干变量。

# 题解二：Knuth-Morris-Pratt 算法

思路及算法

$Knuth-Morris-Pratt$ 算法，简称 $KMP$ 算法，由 $Donald Knuth$、$James H. Morris$ 和 $Vaughan Pratt$ 三人于 $1977$ 年联合发表。

$Knuth-Morris-Pratt$ 算法的核心为前缀函数，记作 $\pi(i)$ ，其定义如下:

对于长度为 $m$ 的字符串 $s$ ，其前缀函数 $\pi(i)(0 \leq i<m)$ 表示 $s$ 的子串 $s[0: i]$ 的最长的相等的真前缀与真后缀的长度。特别地，如果不存在符合条件的前后缀，那么 $\pi(i)=0$ 。其中真前缀与真后缀的定义为不等于自身的的前缀与后缀。

我们举个例子说明：字符串 $a a b a a a b$ 的前缀函数值依次为 $0,1,0,1,2,2,3$ 。

- $\pi(0)=0$ ，因为 $a$ 没有真前缀和真后缀，根据规定为 0 (可以发现对于任意字符串 $\pi(0)=0$必定成立)；
- $\pi(1)=1$ ，因为 $a a$ 最长的一对相等的真前后缀为 $a$ ，长度为 1 ；
- $\pi(2)=0$ ，因为 $a a b$ 没有对应真前缀和真后缀，根据规定为 0 ；
- $\pi(3)=1$ ，因为 $a a b a$ 最长的一对相等的真前后缀为 $a$ ，长度为 1 ；
- $\pi(4)=2$ ，因为 $a a b a a$ 最长的一对相等的真前后缀为 $a a$ ，长度为 2 ；
- $\pi(5)=2$ ，因为 $a a b a a a$ 最长的一对相等的真前后缀为 $a a$ ，长度为 2 ；
- $\pi(6)=3$ ，因为 $a a b a a a b$ 最长的一对相等的真前后缀为 $a a b$ ，长度为 3 。

有了前缀函数，我们就可以快速地计算出模式串在主串中的每一次出现。

**如何求解前缀函数**

长度为 $m$ 的字符串 $s$ 的所有前缀函数的求解算法的总时间复杂度是严格 $O(m)$ 的，且该求解算法是增量算法，即我们可以一边读入字符串，一边求解当前读入位的前缀函数。

为了叙述方便，我们接下来将说明几个前缀函数的性质：
1. $\pi(i) \leq \pi(i-1)+1$ 。
- 依据 $\pi(i)$ 定义得: $s[0: \pi(i)-1]=s[i-\pi(i)+1: i]$ 。
- 将两区间的右端点同时左移，可得: $s[0: \pi(i)-2]=s[i-\pi(i)+1: i-1]$ 。
- 依据 $\pi(i-1)$ 定义得: $\pi(i-1) \geq \pi(i)-1$ ，即 $\pi(i) \leq \pi(i-1)+1$ 。
2. 如果 $s[i]=s[\pi(i-1)]$ ，那么 $\pi(i)=\pi(i-1)+1$ 。
- 依据 $\pi(i-1)$ 定义得: $s[0: \pi(i-1)-1]=s[i-\pi(i-1): i-1]$ 。
- 因为 $s[\pi(i-1)]=s[i]$ ，可得 $s[0: \pi(i-1)]=s[i-\pi(i-1): i]$ 。
- 依据 $\pi(i)$ 定义得: $\pi(i) \geq \pi(i-1)+1$ ，结合第一个性质可得 $\pi(i)=\pi(i-1)+1$ 。

这样我们可以依据这两个性质提出求解 $\pi(i)$ 的方案：找到最大的 $j$ ，满足 $s[0: j-1]=s[i-j$ : $i-1]$, 且 $s[i]=s[j]$ (这样就有 $s[0: j]=s[i-j: i]$ ，即 $\pi(i)=j+1$ )。

注意这里提出了两个要求:
1. $j$ 要求尽可能大，且满足 $s[0: j-1]=s[i-j: i-1]$ ；
2. $j$ 要求满足 $s[i]=s[j]$ 。

由 $\pi(i-1)$ 定义可知:
$$
s[0: \pi(i-1)-1]=s[i-\pi(i-1): i-1]
$$

那么 $j=\pi(i-1)$ 符合第一个要求。如果 $s[i]=s[\pi(i-1)]$ ，我们就可以确定 $\pi(i)$ 。
否则如果 $s[i] \neq s[\pi(i-1)]$ ，那么 $\pi(i) \leq \pi(i-1)$ ，因为 $j=\pi(i)-1$ ，所以 $j<\pi(i-1)$ ，于是可以取 (1) 式两子串的长度为 $j$ 的后缀，它们依然是相等的: $s[\pi(i-1)-j: \pi(i-1)-1]=s[i-$ $j: i-1]$ 。

当 $s[i] \neq s[\pi(i-1)]$ 时，我们可以修改我们的方案为: 找到最大的 $j$ ，满足 $s[0: j-1]=s[\pi(i-$ 1) $-j: \pi(i-1)-1]$, 且 $s[i]=s[j]$ (这样就有 $s[0: j]=s[\pi(i-1)-j: \pi(i-1)]$, 即 $\pi(i)=$ $\pi(i-1)+1)$ 。

注意这里提出了两个要求:

1. $j$ 要求尽可能大，且满足 $s[0: j-1]=s[\pi(i-1)-j: \pi(i-1)-1]$ ；
2. $j$ 要求满足 $s[i]=s[j]$ 。

由 $\pi(\pi(i-1)-1)$ 定义可知 $j=\pi(\pi(i-1)-1)$ 符合第一个要求。如果 $s[i]=s[\pi(\pi(i-1)-1)]$,我们就可以确定 $\pi(i)$ 。

此时，我们可以发现 $j$ 的取值总是被描述为 $\pi(\pi(\pi(\ldots)-1)-1)$ 的结构（初始为 $\pi(i-1)$ )。于是我们可以描述我们的算法: 设定 $\pi(i)=j+1 ， j$ 的初始值为 $\pi(i-1)$ 。我们只需要不断迭代 $j$ (令 $j$ 变为 $\pi(j-1)$ ) 直到 $s[i]=s[j]$ 或 $j=0$ 即可，如果最终匹配成功（找到了 $j$ 使得 $s[i]=$ $s[j]$ )，那么 $\pi(i)=j+1$ ，否则 $\pi(i)=0$ 。

复杂度证明
时间复杂度部分，注意到 $\pi(i) \leq \pi(i-1)+1$ ，即每次当前位的前缀函数至多比前一位增加一，每当我们迭代一次，当前位的前缀函数的最大值都会减少。可以发现前缀函数的总减少次数不会超过总增加次数，而总增加次数不会超过 $m$ 次，因此总减少次数也不会超过 $m$ 次，即总迭代次数不会超过 $m$ 次。

空间复杂度部分，我们只用到了长度为 $m$ 的数组保存前缀函数，以及使用了常数的空间保存了若干变量。

如何解决本题

记字符串 haystack 的长度为 $n$ ，字符串 needle 的长度为 $m$ 。
我们记字符串 $s t r=n e e d l e+\#+$ haystack，即将字符串 needle 和 haystack 进行拼接，并用不存在于两串中的特殊字符 \# 将两串隔开，然后我们对字符串 $s t r$ 求前缀函数。

因为特殊字符 $\#$ 的存在，字符串 str 中 haystack 部分的前缀函数所对应的真前缀必定落在字符串 needle 部分，真后缀必定落在字符串 haystack 部分。当 haystack 部分的前缀函数值为 $m$ 时，我们就找到了一次字符串 needle 在字符串 haystack 中的出现（因为此时真前缀恰为字符串 needle）。

实现时，我们可以进行一定的优化，包括：
1. 我们无需显式地创建字符串 $s t r$ 。
- 为了节约空间，我们只需要顺次遍历字符串 needle、特殊字符\# 和字符串 haystack 即可。
2. 也无需显式地保存所有前缀函数的结果，而只需要保存字符串 needle 部分的前缀函数即可。
- 特殊字符 $\#$ 的前缀函数必定为 0 ，且易知 $\pi(i) \leq m$ (真前缀不可能包含特殊字符 \#)。
- 这样我们计算 $\pi(i)$ 时， $j=\pi(\pi(\pi(\ldots)-1)-1)$ 的所有的取值中仅有 $\pi(i-1)$ 的下标可能大于等于 $m$ 。我们只需要保存前一个位置的前缀函数，其它的 $j$ 的取值将全部为字符串 needle 部分的前缀函数。
3. 我们也无需特别处理特殊字符 \#，只需要注意处理字符串 haystack 的第一个位置对应的前缀函数时，直接设定 $j$ 的初值为 0 即可。

1. 第一部分是求 needle 部分的前缀函数，我们需要保留这部分的前缀函数值。
2. 第二部分是求 haystack 部分的前缀函数，我们无需保留这部分的前缀函数值，只需要用一个变量记录上一个位置的前缀函数值即可。当某个位置的前缀函数值等于 $m$ 时，说明我们就找到了一次字符串 needle 在字符串 haystack 中的出现（因为此时真前缀恰为字符串 needle，真后缀为以当前位置为结束位置的字符串 haystack 的子串)，我们计算出起始位置，将其返回即可。

![找出字符串中第一个匹配项的下标(题解二）](https://qncdn.oleehu.xyz/blog/LeetCode/%E6%89%BE%E5%87%BA%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%8C%B9%E9%85%8D%E9%A1%B9%E7%9A%84%E4%B8%8B%E6%A0%87%28%E9%A2%98%E8%A7%A3%E4%BA%8C%29.png)


```c++
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};
```
复杂度分析

时间复杂度：$O(n+m)$，其中 $n$ 是字符串 $haystack$ 的长度，mmm 是字符串 $needle$ 的长度。我们至多需要遍历两字符串一次。

空间复杂度：$O(m)$，其中 $m$ 是字符串 $needle$ 的长度。我们只需要保存字符串 $needle$ 的前缀函数。

LeetCode（找出字符串中第一个匹配项的下标）

# 时间表示法

让我们先了解两个时间测量值的区别：
  1. 挂钟时间
    从开始执行到完成的时间，包括等待其他系统活动和应用程序的时间
  2. 模拟时间
    模拟建模的时间，可能小于或大于模拟的挂钟时间。

在 `systemC` 中，`sc_time` 是模拟内核用于跟踪模拟时间的数据类型。它定义了几个时间单位：
`SC_SEC`、`SC_MS、SC_US`、`SC_NS`、`SC_PS SC_FS`。每个后续时间单位是其前一个时间单位的 `1/1000`。

`sc_time`对象可用作赋值、算术和比较运算的操作数：
  乘法允许其操作数之一为双精度
  除法允许除数为双精度

`SC_ZERO_TIME`：
一个表示时间值为零的宏。每当写入时间值为零时（例如，创建增量通知或增量超时时），最好使用此常量。

要获取当前模拟时间，请使用 `sc_time_stamp（）`。



# Time_Notation.cpp


```c++
#include <systemc>
using namespace sc_core;

int sc_main(int, char*[]) {
sc_core::sc_report_handler::set_actions( "/IEEE_Std_1666/deprecated",
                                           sc_core::SC_DO_NOTHING ); // 禁止因set_time_resolution而发出的警告
  sc_set_time_resolution(1, SC_FS); // 已弃用函数，但仍然有用，默认值为 1 PS
  sc_set_default_time_unit(1, SC_SEC); // change time unit to 1 second
  std::cout << "1 SEC =     " << sc_time(1, SC_SEC).to_default_time_units() << " SEC"<< std::endl;
  std::cout << "1  MS = " << sc_time(1, SC_MS).to_default_time_units()  << " SEC"<< std::endl;
  std::cout << "1  US = " << sc_time(1, SC_US).to_default_time_units()  << " SEC"<< std::endl;
  std::cout << "1  NS = " << sc_time(1, SC_NS).to_default_time_units()  << " SEC"<< std::endl;
  std::cout << "1  PS = " << sc_time(1, SC_PS).to_default_time_units()  << " SEC"<< std::endl;
  std::cout << "1  FS = " << sc_time(1, SC_FS).to_default_time_units()  << " SEC"<< std::endl;
  sc_start(7261, SC_SEC); // 运行模拟 7261 秒
  double t = sc_time_stamp().to_seconds(); // 以秒为单位获取时间
  std::cout << int(t) / 3600 << " hours, " << (int(t) % 3600) / 60 << " minutes, " << (int(t) % 60) << "seconds" << std::endl;
  return 0;
}

```

# 结果


```shell
        SystemC 2.3.3-Accellera --- Oct  4 2020 22:59:38
        Copyright (c) 1996-2018 by all Contributors,
        ALL RIGHTS RESERVED
1 SEC =     1 SEC
1  MS = 0.001 SEC
1  US = 1e-06 SEC
1  NS = 1e-09 SEC
1  PS = 1e-12 SEC
1  FS = 1e-15 SEC
2 hours, 1 minutes, 1seconds
```

编译U-Boot

开发环境搭建

半加器

找出字符串中第一个匹配项的下标

时间表示法