【编码狂想】深度探索C++编程之旅:“数组、字符串、函数与KMP算法解密“

简介: 【编码狂想】深度探索C++编程之旅:“数组、字符串、函数与KMP算法解密“



🌐第一部分 数组篇

😎1.1 获取数组最值

描述

键盘随机输入 6 个整数,将这些数据保存到数组中,获取数组中的最小值和最大值并输出。

输入描述:

键盘随机输入 6 个整数

输出描述:

输出数组中的最小值和最大值,两个值中间使用空格隔开

示例1

输入:
5
12
80
7
15
60
输出:
5 80

💡解决如下:

#include <iostream>
using namespace std;
//获取数组最小值
int Min(int a[],int n){
    int min=a[0];
    for(int i=0;i<n;i++){
        if(min>a[i]) min=a[i];
    }
    return min;
}
//获取数组最大值
int Max(int a[],int n){
    int max=a[0];
    for(int i=0;i<n;i++){
        if(max<a[i]) max=a[i];
    }
    return max;
}
int main() {
    int a[6];
    int n=sizeof(a)/sizeof(a[0]);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<Min(a,n)<<" "<<Max(a, n)<<endl;
    return 0;
}

😎1.2 数组元素反转

描述

键盘随机输入 6 个整数,将这些数据保存到数组中,先将数组中元素按照格式输出,然后再将数组元素反转,最后按照格式再次输出数组元素。

输入描述:

键盘随机输入 6 个整数

输出描述:

第一次按照格式输出数组中元素,每个元素中间使用逗号和空格隔开,整体使用中括号括起来。

例如:[5, 12, 80, 7, 15, 60]

第二次按照格式输出反转后数组中元素,每个元素中间使用逗号和空格隔开,整体使用中括号括起来。

例如:[60, 15, 7, 80, 12, 5]

示例1

输入:
5
12
80
7
15
60
输出:
[5, 12, 80, 7, 15, 60]
[60, 15, 7, 80, 12, 5]

💡解决如下:

#include <iostream>
using namespace std;
//输出数组
void Disp(int a[],int n){
    cout<<"[";
    for(int i=0;i<n-1;i++){
        cout<<a[i]<<", ";
    }
    cout<<a[n-1]<<"]"<<endl;
}
//翻转数组
void func(int a[],int n){
    for(int i=0;i<n/2;i++){
        int t=a[i];
        a[i]=a[n-i-1];
        a[n-i-1]=t;
    }
}
int main(){
    int a[6];
    int n=sizeof(a)/sizeof(a[0]);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    Disp(a,n);
    func(a, n);
    Disp(a,n);
    return 0;
}

😎1.3 C++冒泡排序

描述

键盘随机输入 6 个整数,将这些数据保存到数组中,使用冒泡排序对数组中的元素进行从小到大顺序排序,输出排序后数组中的元素(元素之间使用空格隔开)。

输入描述:

键盘随机输入 6 个整数

输出描述:

输出排序后数组中的元素(元素之间使用空格隔开)

示例1

输入:
24
69
80
57
13
16
输出:
13 16 24 57 69 80

💡解决如下:

#include <iostream>
#include <linux/limits.h>
using namespace std;
//冒泡排序
void MpSort(int a[],int n){
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-1-i;j++){
            if(a[j]>a[j+1]){
                int t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
}
//输出数组
void Disp(int a[],int n){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
int main() {
    int a[6];
    int n=sizeof(a)/sizeof(a[0]);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    MpSort(a,n);
    Disp(a,n);
    return 0;
}

😎1.4 C++选择排序

题目同1.3

💡解决如下:

#include <iostream>
#include <linux/limits.h>
using namespace std;
//选择排序
void ChooseSort(int a[],int n){
    for(int i=0;i<n-1;i++){
        int k=i;
        for(int j=i+1;j<n;j++){
            if(a[k]>a[j]){
                int t=a[k];
                a[k]=a[j];
                a[j]=t;
            }
        }
    }
}
//输出数组
void Disp(int a[],int n){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
int main() {
    int a[6];
    int n=sizeof(a)/sizeof(a[0]);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    ChooseSort(a,n);
    Disp(a,n);
    return 0;
}

😎1.5 C++快速排序

题目同1.3

💡解决如下:

#include <iostream>
#include <linux/limits.h>
using namespace std;
//快速排序
void FastSort(int a[],int L,int R){
    int left=L,right=R;
    int pivot=a[left];
    while(left<right){
        while (left<right && pivot<=a[right]) {
            right--;
        }
        if(left<right){
            a[left]=a[right];
        }
        while (left<right && pivot>=a[left]) {
            left++;
        }
        if(left<right){
            a[right]=a[left];
        }
        if(left>=right){
            a[right]=pivot;
        }
        FastSort(a, L, left-1);
        FastSort(a, left+1, R);
    }
}
//输出数组
void Disp(int a[],int n){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
int main() {
    int a[6];
    int n=sizeof(a)/sizeof(a[0]);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    FastSort(a,0,n-1);
    Disp(a,n);
    return 0;
}

😎1.6 计算公司年销售额

描述

某公司按照季度和每个季度对应3个月份统计的数据如下:单位(万元)

第一季度:22,66,44

第二季度:77,33,88

第三季度:25,45,65

第四季度:11,66,99

请使用二维数组保存这些数据,并计算公司年销售总额。

输入描述:

输出描述:

输出公司年销售总额

💡解决如下:

#include <iostream>
using namespace std;
//求和
int AddSum(int a[4][3]){
    int sum=0;
    for(int i=0;i<4;i++){
        for(int j=0;j<3;j++){
            sum+=a[i][j];
        }
    }
    return sum;
}
int main() {
    int a[4][3]={
        {22,66,44},
        {77,33,88},
        {25,45,65},
        {11,66,99}
    };
    cout<<AddSum(a)<<endl;
    return 0;
}

🌐第二部分 字符串篇

😎2.1 改进strcat

描述

键盘输入两个字符串,将这两个字符串进行拼接后输出。

输入描述:

键盘输入两个字符串

输出描述:

输出两个字符串拼接后的结果

示例1

输入:
hello
nihao
输出:
hellonihao

💡解决如下:

C++很简单,主要是使用C语言解决问题。

#include <cstring>
#include <iostream>
#include <string>
using namespace std;
//拼接字符串
string merge(string s1,string s2){
    string s;
    s=s1+s2;
    return s;
}
int main() {
    string s1,s2;
    getline(cin,s1);
    getline(cin,s2);
    cout<<merge(s1, s2)<<endl;
    return 0;
}

C语言的解决方案:用到了函数指针和指针函数,稍微炫下技哈哈

#include <stdio.h>
#include <string.h>
//改进strcat
char * merge(char *ch1,char *ch2){//指针函数
    char * sum=malloc(strlen(ch1)+strlen(ch2)+1);
    strcpy(sum, ch1);
    strcat(sum, ch2);
    return sum;
}
int main() {
    char * (*p)(char *,char *)=merge;//函数指针
    const int MaxSize=100;
    char ch1[MaxSize],ch2[MaxSize];
    fgets(ch2,MaxSize,stdin);
    fgets(ch1,MaxSize,stdin);
    //去除换行符
    ch1[strcspn(ch1, "\n")]='\0';
    ch2[strcspn(ch2, "\n")]='\0';
    char *c1=ch2,*c2=ch1;
    printf("%s",p(c1,c2));
    return 0;
}

🌐第三部分 new\delete篇

😎3.1 创建动态数组

描述

键盘输入一个正整数 n,创建大小为 n 的数组(采用动态数组的方式),将数组中的元素初始化为 n、n+1、...、2n - 1。并输出数组中的元素。

输入描述:

键盘输入一个正整数 n

输出描述:

输出数组中的元素,元素和元素之间使用空格隔开

示例1

输入:
3
输出:
3 4 5

💡解决如下:

#include <iostream>
#include <unistd.h>
using namespace std;
//赋值
void func(int *a,int n){
    for(int i=0;i<n;i++){
        a[i]=n+i;
    }
}
//输出
void Disp(int *a,int n){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
int main() {
    int n;
    cin >> n;
    int *a=new int[n];
    //int *a=(int *)malloc(sizeof(int)*n);
    func(a,n);
    Disp(a,n);
    delete [] a;
    //free(a);
    return 0;
}

😎3.2 创建二维动态数组

描述

输入一个正整数 n,创建大小为 n∗n的二维数组a(采用动态数组的方式),将a[i][j]初始化为i+j(0≤i<n,0≤j<n)。并输出数组中的元素。

输入描述:

输入一个正整数 n

输出描述:

输出n行,每行n个用空格隔开的整数表示数组a,知识详见

示例1

输入:
2
输出:
0 1
1 2

💡解决如下:

#include<bits/stdc++.h>
using namespace std;
//赋值
void func(int **a,int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a[i][j]=i+j;
        }
    }
}
//输出
void Disp(int **a,int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}
int main(){
    int n;
    cin>>n;
    int k=n;//创建a[n][k]
    int **a=new int*[n];
    for(int i=0;i<n;i++){
        a[i]=new int[k];
    }
    func(a,n);
    Disp(a, n);
    //释放
    for(int i=0;i<n;i++){
        delete [] a[i];
    }
    delete [] a;
    return 0;
}

🌐第四部分 函数篇

😎4.1 数组元素处理

描述

有一个数组 int arr[n],要求写一个函数:void func(int *p, int n);将数组 arr 中为 0 的元素都移至数组末尾,将非 0 的元素移至开始(保持原来的顺序不变)。

例如:

数组中元素原来是:1 0 3 4 0 -3 5

经过 func 处理后:1 3 4 -3 5 0 0

输入描述:

键盘输入 6 个整数,保存到数组中

输出描述:

经过 func 处理后数组的元素,元素和元素之间使用空格隔开

例如:1 3 4 -3 5 0 0

示例1

输入:
1
0
3
4
0
-3
输出:
1 3 4 -3 0 0

💡解决如下:

#include <iostream>
using namespace std;
void func(int *a,int n){//将数组 arr 中为 0 的元素都移至数组末尾,将非 0 的元素移至开始(保持原来的顺序不变)
    int *b=new int[n];
    int count=0;//统计0的数量
    //b[]即为所求
    for(int i=0,k=0;i<n;i++){
        if(a[i]!=0){
            b[k]=a[i];
            k++;
        }
        else count++;
    }
    for(int i=0;i<count;i++){
        b[n-i-1]=0;
    }
    for(int i=0;i<n;i++){
        a[i]=b[i];
    }
    delete [] b;
}
int main(){
    int n=6;
    int *a=new int[n];
    for(int i=0;i<n;i++){//赋值
        cin>>a[i];
    }
    func(a,n);
    for(int i=0;i<n;i++){//输出
        cout<<a[i]<<" ";
    }
    cout<<endl;
    delete [] a;
}

😎4.2 比较字符串大小

描述

编写一个函数 int mystrcmp(const char * src, const char * dst),用于比较两个字符串的大小(自己实现strcmp()函数)。要求如果字符串src大于字符串dst返回 1,小于返回 -1,相等返回 0。

输入描述

键盘录入 2 个长度小于 100 的字符串

输出描述:

输出调用 mystrcmp() 函数返回的结果

示例1

输入:
hello
helloworld
输出:
-1

💡解决如下:

#include <iostream>
#include <cstring>
using namespace std;
int mystrcmp(string * p1, string * p2){
    if(*p1 == *p2) return 0;
    else if(*p1>*p2) return 1;
    else return -1;
}
int main(){
    string s1,s2;
    getline(cin,s1);
    getline(cin,s2);
    string *p1=&s1;
    string *p2=&s2;
    cout<<mystrcmp(p1,p2);
    return 0;
}

😎4.3 使用字符函数统计字符串中各类型字符的个数

描述

键盘录入一句话,统计这句话中字母字符、数字字符、空白、标点符号和其它字符的个数。(使用字符函数实现)

输入描述:

键盘输入一个字符串

输出描述:

输出字符串中字母字符、数字字符、空白、标点符号和其它字符的个数。

示例1

输入:
hello123world,$ 123
输出:
chars : 10 whitespace : 1 digits : 6 others : 2

💡解决如下:

#include <iostream>
#include <string>
using namespace std;
//处理输出
void func(string s){
    int whitespace = 0;
    int digits = 0;
    int chars = 0;
    int others = 0;
    for(int i=0;s[i]!='\0';i++){
        if(s[i]>='A' &&s[i]<='z'){//'A':65,'a':97
            chars++;
        }
        else if(s[i]>='0'&&s[i]<='9'){
            digits++;
        }
        else if(s[i]==' '){
            whitespace++;
        }
        else others++;
    }
    cout<< "chars : " << chars<< " whitespace : " << whitespace<< " digits : " << digits<< " others : " << others << endl;
}
int main() {
    string s;
    getline(cin,s);
    func(s);
    return 0;
}

😎4.4 函数实现计算一个数的阶乘

描述

编写一个函数 long long factorial(int n),用于计算 n 的阶乘。(要求使用递归实现)

输入描述:

键盘输入任意一个整数 n ,范围为 1 - 20

输出描述:

输出 n 的阶乘

示例1

输入:
5
输出:
120

💡解决如下:

#include <iostream>
using namespace std;
long long factorial(int n) {
    if(n==0 || n==1) return 1;
    else return n*factorial(n-1);
}
int main() {
    int n;
    cin >> n;
    cout << factorial(n) << endl;
    return 0;
}

😎4.5 不死神兔问题

描述

有一对兔子,从出生后第 3 个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第 n 个月的兔子对数为多少?

1 1 2 3 5 8...

输入描述:

键盘输入任意一个正整数 n,n 的范围为 [1, 20]

输出描述:

输出第 n 个月兔子的对数

示例1

输入:
1
输出:
1

💡解决如下:

#include <iostream>
using namespace std;
//统计个数
int Sum(int n){
    int *a=new int[n];
    for(int i=0;i<n;i++){
        if(i==0 || i==1) a[i]=1;
        else a[i]=a[i-1]+a[i-2];
    }
    return a[n-1];
    delete [] a;
}
int main(){
    int n;
    cin>>n;
    cout<<Sum(n)<<endl;
    return 0;
}

😎4.6 统计字符串中各类型字符的个数

描述

键盘输入两个字符串 str 和 substr,统计字符串 substr 在 字符串 str 中出现的次数,并输出。  

输入描述:

键盘输入两个长度小于 100 的字符串 str 和 substr

输出描述:

输出字符串 substr 在 字符串 str 中出现的位置,从0开始。

示例1

输入:
nihaohello
hello
输出:
5

💡解决如下:

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    int letter = 0;
    int digit = 0;
    int space = 0;
    int other = 0;
    char buf[1024] = {0};
    cin.getline(buf, sizeof(buf));
    // write your code here......
    //for(int i=0;buf[i]!='\0';i++){
    for(int i=0;i<int(strlen((buf)));i++){//这两个都可以
        if(buf[i]>='A' && buf[i]<='z') letter++;
        else if(buf[i]>='0' && buf[i]<='9') digit++;
        else if(buf[i]==' ') space++;
        else other++;
    }
    cout << "letter:" << letter << " digit:" << digit << " space:" << space << " other:" << other << endl;
    return 0;
}

😎4.7 个人所得税计算程

描述

个人所得税是国家对本国公民、居住在本国境内的个人的所得和境外个人来源于本国的所得征收的一种所得税。假设某地区的起征点为3500元(即月工资低于3500时不需要缴纳个人所得税),个人所得税的计算公式为:应纳税额 =(工资薪金所得-扣除数)× 适用税率-速算扣除数。其中,扣除数为3500元,适用税率以及速算扣除数如下表所示。

表-1 个人所得税缴纳标准

全月应纳税所得额

   税率   

   速算扣除数(元)   

  不超过1500元

   3%

      0

  超过1500元至4500元

   10%

     105

 超过4500元至9000元

   20%

     555

  超过9000元至35000元

   25%

     1005

 超过35000元至55000元      

   30%

     2755

  超过55000元至80000元  

   35%

     5505

  超过80000元

   45%

     13505

上表中的全月应纳税所得额 = 工资薪金所得-扣除数。

现在请你补全代码中的 Employee 类,新建三个 Employee 对象,姓名分别是张三,李四和王五,他们的月工资分别为 6500,8000,100000。并将他们存入一个 STL 容器中,要求按照月工资由高到底的顺序排序,遍历容器并计算他们应缴纳的个人所得税(个人所得税为 double 类型,保留一位小数)。

输入描述:

输出描述:

王五应该缴纳的个人所得税是:xxx

李四应该缴纳的个人所得税是:xxx

张三应该缴纳的个人所得税是:xxx

💡解决如下:

#include <iostream>
#include <iomanip>
using namespace std;
class Employee {
    private:
        string name;
        double salary;
    public:
        //构造函数
        Employee(){}
        Employee(string name,double salary){
            this->name=name;this->salary=salary;
        }
        void func(){
            int income=salary-3500;
            double tax=0;
            if(income>80000) tax=income*0.45-13505;
            else if(income>=55000) tax=income*0.35-5505;
            else if(income>=35000) tax=income*0.3-2755;
            else if(income>=9000) tax=income*0.25-1005;
            else if(income>=4500) tax=income*0.2-555;
            else if(income>=1500) tax=income*0.1-105;
            else if(income>=0) tax=income*0.03;
            else tax=0;
            cout<<fixed<<setprecision(1)<<name<<"应该缴纳的个人所得税是:"<<tax<<endl;
        }
};
int main() {
    Employee zs("张三",6500),ls("李四",8000),ww("王五",100000);
    ww.func();
    ls.func();
    zs.func();
    return 0;
}

😎4.8 实现简单计算器功能

描述

键盘输入一个字符串,格式:运算方式 整数1 整数2,编写程序解析出字符串中的 3 部分内容,然后做相应的运算,并输出结果。

例如:

输入“add 10 20”,则做加法运算(10+20);

输入“sub 10 20”,则做减法运算(10-20);

输入“mul 10 20”,则做乘法运算(10*20);

输入“div 10 20”,则做除法运算(10/20),如果除数为 0,则不做运算,输出“Error”;

注意:运算方式忽略大小写,即 “add” 同 “Add”、“ADD”等。

输入描述:

键盘输入一个字符串,格式:运算方式 整数1 整数2

整数范围为[-100, 100]

输出描述:

输出运算后的结果(除法不考虑小数),如果除数为 0,则不做运算,输出“Error”

示例1

输入:
add 10 3
输出:
13

💡解决如下:

#include <iostream>
using namespace std;
int main() {
    string s;
    int a,b;
    cin>>s>>a>>b;
    if(s=="add") cout<<a+b<<endl;
    else if(s=="sub") cout<<a-b<<endl;
    else if(s=="mul") cout<<a*b<<endl;
    else if(s=="div" && b!=0) cout<<double(a/b)<<endl;
    else cout<<"Error"<<endl;
    return 0;
}

😎4.9 十进制整数转十六进制字符串

描述

编写一个函数,传入一个十进制的正整数,将十进制整数转换为十六进制的字符串并返回。(十六进制字符串中的字母全部大写)

输入描述:

键盘输入一个十进制的正整数

输出描述:

输出该十进制整数转换后的十六进制字符串

示例1

输入:
162
输出:
A2

💡解决如下:

#include <iostream>
#include <string>
using namespace std;
void inv(string &s){
    int slen=s.length();
    for(int i=0;i<slen/2;i++){
        char ch=s[i];
        s[i]=s[slen-i-1];
        s[slen-i-1]=ch;
    }
}
string toHexString(int n) {
    string s;
    int num=n,k=16;
    int value=num-16*int(num/k);
    for(;value!=0;){
        char ch;
        if(value>=0 && value<=9) ch=48+value;
        else ch=65+(value-10);
        s+=ch;//s目前只是顺序存储商,还需要翻转
        num=int(num/k);
        value=num-16*int(num/k);
    }
    string &ss=s;
    inv(ss);
    return s;
}
int main() {
    int n;
    cin >> n;
    cout <<toHexString(n)<< endl;
    return 0;
}

😎4.10 质数累乘

示例1

输入:
12
输出:
12=2*2*3

💡解决如下:

#include <iostream>
#include <vector>
using namespace std;
int ZS(int n){//判断是否是质数,返回1则是,否则不是
    if(n<=1) return -1;
    for(int i=2;i<=n;i++){
        if(n==i) return 1;
        if(n%i==0) return -1;
    }
    return 0;
}
void func(int n){//将数转换成质数的累乘
    vector<int> v;
    int mul=1,num=n;
    for(int i=2;i<n;i++){
        while(ZS(i)!=0 && num%i==0){
            v.push_back(i);
            mul*=i;
            num=num/i;
            if(mul==n) break;
        }
        if(mul==n) break;
    }
    int vlen=v.size();
    if(vlen<=0) cout<<"error!\n";
    else if(vlen==1) cout<<n<<"="<<v[0];
    else{
        cout<<n<<"="<<v[0];
        for(int i=1;i<vlen;i++){
            cout<<"*"<<v[i];
        }
        cout<<endl;
    }
}
int main(){
    int n;
    cin>>n;
    func(n);
    return 0;
}

🌐第五部分 模式匹配篇

😎5.1 KMP或暴力搜索

描述

键盘输入两个字符串 str 和 substr,统计字符串 substr 在 字符串 str 中出现的次数,并输出。  

输入描述:

键盘输入两个长度小于 100 的字符串 str 和 substr

输出描述:

输出字符串 substr 在 字符串 str 中出现的位置,从0开始。

示例1

输入:
nihaohello
hello
输出:
5

💡解决如下:

暴力搜索BF

#include <iostream>
#include <cstring>
using namespace std;
//BF
int BF(string s1,string s2){
    int i=0,j=0;
    for(;i<s1.length() && j<s2.length();){
        if(s1[i]==s2[j]){
            i++;j++;
        }
        else {
            i=i-j+1;
            j=0;
        }
    }
    if(j>=s2.length()){
        return (i-s2.length());
    }
    else return -1;
}
int main(){
    string s1,s2;
    getline(cin,s1);
    getline(cin,s2);
    cout<<BF(s1,s2)<<endl;
    return 0;
}

KMP

#include <iostream>
#include <string>
using namespace std;
/*KMP算法*/
//求next[]
void getNext(string t,int next[]){
    int j=0,k=-1;//j扫描t,k记录t[j]之前与t首字符相同的个数
    next[0]=-1;
    for(;j<t.length();){//next[0]已经给了,剩下的t.length()-1
        if(k==-1 || t[j]==t[k]){
            j++;k++;
            next[j]=k;
        }
        else k=next[k];
    }
}
//KMP
int KMP(string s,string t){
    int tlen=t.length();
    int slen=s.length();
    int *next=new int[tlen];
    getNext(t,next);
    int i=0,j=0;
    while(i<slen && j<tlen){
        if(j==-1 || s[i]==t[j]){
            i++;
            j++;
        }
        else{
            j=next[j];
        }
    }
    delete [] next;
    if(j>=tlen) return (i-tlen);
    else return (-1);
}
int main(){
    string s1,s2;
    getline(cin,s1);//helloworld
    getline(cin,s2);//wo
    cout<<KMP(s1,s2)<<endl;
    return 0;
}

😎5.2 统计字符串中子串出现的次数

描述

键盘输入两个字符串 str 和 substr,统计字符串 substr 在 字符串 str 中出现的次数,并输出。  

输入描述:

键盘输入两个长度小于 100 的字符串 str 和 substr

输出描述:

输出字符串 substr 在 字符串 str 中出现的次数

示例1

输入:
nihaohellowoshihello
hello
输出:
2

💡解决如下:

暴力搜索BF

#include <iostream>
#include <cstring>
using namespace std;
//BF
int BF(string s1,string s2){
    int i=0,j=0;
    int count=0;
    for(;i<s1.length() && j<s2.length();){
        if(s1[i]==s2[j]){
            i++;j++;
        }
        else {
            i=i-j+1;
            j=0;
        }
        if(j>=s2.length()){
            i=i-j+1;
            j=0;
            count++;
        }
    }
    return count;
}
int main(){
    string s1,s2;
    getline(cin,s1);
    getline(cin,s2);
    cout<<BF(s1,s2)<<endl;
    return 0;
}

KMP

#include <iostream>
#include <string>
using namespace std;
/*KMP算法*/
//求next[]
void getNext(string t,int next[]){
    int j=0,k=-1;//j扫描t,k记录t[j]之前与t首字符相同的个数
    next[0]=-1;
    for(;j<t.length();){//next[0]已经给了,剩下的t.length()-1
        if(k==-1 || t[j]==t[k]){
            j++;k++;
            next[j]=k;
        }
        else k=next[k];
    }
}
//KMP
int KMP(string s,string t){
    int tlen=t.length();
    int slen=s.length();
    int *next=new int[tlen];
    int count=0;
    getNext(t,next);
    int i=0,j=0;
    while(i<slen && j<tlen){
        if(j==-1 || s[i]==t[j]){
            i++;
            j++;
            if(j>=tlen){
                count++;
                j=next[j];
            }
        }
        else{
            j=next[j];
        }
    }
    delete [] next;
    return count;
}
int main(){
    string s1,s2;
    getline(cin,s1);//helloworld
    getline(cin,s2);//wo
    cout<<KMP(s1,s2)<<endl;
    return 0;
}

目录
相关文章
|
7天前
|
存储 算法
图解Kmp算法——配图详解(超级详细)
图解Kmp算法——配图详解(超级详细)
|
10天前
|
编译器 C语言 C++
【C++初阶(九)】C++模版(初阶)----函数模版与类模版
【C++初阶(九)】C++模版(初阶)----函数模版与类模版
18 0
|
12天前
|
算法 测试技术 C#
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
|
12天前
|
算法
【算法学习--字符串】(不含KMP算法)
【算法学习--字符串】(不含KMP算法)
|
21天前
|
存储 缓存 C++
C++链表常用的函数编写(增查删改)内附完整程序
C++链表常用的函数编写(增查删改)内附完整程序
|
3天前
|
存储 安全 C语言
【C++】string类
【C++】string类
|
存储 编译器 Linux
标准库中的string类(中)+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
标准库中的string类(中)+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
|
5天前
|
编译器 C++
标准库中的string类(上)——“C++”
标准库中的string类(上)——“C++”
|
5天前
|
编译器 C++
自从学了C++之后,小雅兰就有对象了!!!(类与对象)(中)——“C++”
自从学了C++之后,小雅兰就有对象了!!!(类与对象)(中)——“C++”
|
5天前
|
存储 编译器 C++
自从学了C++之后,小雅兰就有对象了!!!(类与对象)(上)——“C++”
自从学了C++之后,小雅兰就有对象了!!!(类与对象)(上)——“C++”