KMP算法

开在全局变量的数
string a, b;
int ne[1000010];

void pre_ne()  //给a字符串定义ne值
{
  for (int i = 2, j = 0; a[i]; i++)
        //j代表的是a字符串的前导" " i是指从第二个开始匹配 因为第一个肯定是0
  {

    while (j && a[i] != a[j + 1]) j = ne[j];
        //如果此时j不是指向" "并且a字符串的第j+1个值与i个值不相等 则j回到     ne[j] 的位置
    if (a[i] == a[j + 1]) j++;
        //如果相等 j 指向 j 的下一位 在下次循环中i也指向了i的下一位
    ne[i] = j;//否则就把j赋值给此时i的ne值
  }
}

void kmp()//匹配a b字符串
{
  for (int i = 1, j = 0; b[i]; i++)
        //i是指b字符串的下标 j是指a字符串的下标
  {
    while (j && b[i] != a[j + 1])j = ne[j];
    if (b[i] == a[j + 1])j++; //如果两个数相等 则j指向j的下一位
    if (j == a.size() - 1) //有前导" " 所以长度-1 
    {
      //ans++ 如果有求个数 用ans计数
      cout << i - j + 1 << endl;
      j = ne[j];
    }
  }

}

int main() //main 函数按照题目中的要求进行书写
{
  cin >> a >> b;
  a = " " + a;
  b = " " + b;
  pre_ne();
  kmp();
  return 0;
}

#include<iomanip>//保留小数位数
#include<iostream> //c++
#include<algorithm> //sort排序
#include<cstring> //字符串
#include<math.h> //abs等函数
#include<map> //map
#include<set>//set
#include<cctype>
#define int long long //不开longlong见祖宗
#define endl '\n' //处理多数据时省时间
using namespace std;

int z[1110][1110];
int people[1110];
int num;
void floyd()
{
    for (int k = 1; k <= num; k++)
    {
        for (int i = 1; i <= num; i++)
        {
            for (int j = 1; j <= num; j++)
            {
                z[i][j] = min(z[i][k] + z[k][j],z[i][j]);
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); //cin减少时间
    cout.tie(0); //cout减少时间
    cin >> num;
    //初始化自己到自己的距离为0 其他的都为无穷大
    for (int i = 1; i <= num; i++)
    {
        for (int j = 1; j <= num; j++)
        {
            if (i == j) z[i][j] = 0;
            else z[i][j] = 0x3f3f3f3f;
        }
    }
    for (int i = 1; i <= num; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        //记录当前医院的人数为a
        people[i] = a;
        if (b)
        {
            //双向的权值都赋值为1
            z[i][b] = 1;
            z[b][i] = 1;
        }
        if (c)
        {
            z[i][c] = 1;
            z[c][i] = 1;
        }
    }
    //使得两点的距离最小
    floyd();
    int ans = 0x3f3f3f3f;//先定义答案为无穷大
    //外层for循环定义结点 内层for循坏找答案
    for (int i = 1; i <= num; i++)
    {
        int sum = 0;
        for (int j = 1; j <= num; j++)
        {
            sum = sum + people[j] * z[i][j];//当前结点人数=j结点人数*ij之间的距离
        }
        ans = min(ans, sum);//找到最小值
    }
    cout << ans;

    return 0;
    //cout << setw(5) << setfill('0') << a << b;// 输出5位，右对齐，不足补0 。
}