我在代码随想录|写代码Day9之28. 实现 strStr(),459. 重复的子字符串,55. 右旋字符串（第八期模拟笔试)

博主介绍: 27dCnc
专题 : 数据结构帮助小白快速入门

28. 实现 strStr()

题目;

代码

1

class Solution {
public:
//KMP
    int strStr(string s, string t) {
        int n = s.size(),m=t.size();
        if(m==0) return 0;
        s.insert(s.begin(),' ');
        t.insert(t.begin(),' ');
        vector<int> next(m+1);
        //处理next数组
        for(int i=2,j=0;i<=m;i++){
            while(j&&t[i]!=t[j+1]) j = next[j];
            if(t[i] == t[j+1]) j++;
            next[i] = j;
        }
        //匹配过程
        for(int i=1,j=0;i<=n;i++){
            while(j&&s[i] != t[j+1]) j = next[j];
            if(s[i]==t[j+1]) j++;
            if(j==m) return i-m;
        }
        return -1;
    }
};

截图思路:
题意就是要我们找一个字符串中有没有另一个字符串,然后如果有返回第一个字符出现的下标
用查找,就是上面的标准KMP写法,也可以用函数

还有其他写法:

2.函数find()查找方法

class Solution {
public:
    int strStr(string haystack, string needle) {
        int x = haystack.find(needle);
        if(x!=string::npos){
            return x;
        }else{
            return -1;
        }
    }
};

class Solution {
public:
    int strStr(string haystack, string needle) {
        int x = haystack.find(needle);
        return x;
    }
};

3

class Solution {
public:
    int strStr(string s, string t) {
        int n = s.size(),m = t.size();
        for(int i=0;i<=n-m;i++){
            int j = i,k=0;
            while(k<m && s[j]==t[k]){
                j++;k++;
            }
            if(k==m) return i;
        }
        return -1;
    }
};

459. 重复的子字符串

题目 :

代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t =s+s;//俩相同字符串相加
        t = t.substr(1,t.size()-2);//suberstr用于提取字符串和copy类似
        //这个将首尾第一个字符串剔除
        int index = t.find(s);//在我们新的字符串中查找s
        if(index != string::npos){
            return 1;
        }else{
            return 0;
        }
    }
};

思路::用俩字符串相连接,构成新的字符串,然后对字符串进行KMP或者BF

55. 右旋字符串（第八期模拟笔试）

代码

/*
* 12/20/tm /诸天神佛,佑我上分
*/

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define PII pair<int,int>
#define ll long long
#define multicase 0
#define N 500005
#define mod 998244353

int a[N], b[N];

void read(int&x) {
    x=0; char ch=getchar(); int f=1;
    while(!isdigit(ch)) f=ch=='-'?-1:1, ch=getchar();
    while(isdigit(ch)) x=x*10+ch-48, ch=getchar();
    x=f*x;
}

void read(ll&x) {
    x=0; char ch=getchar(); int f=1;
    while(!isdigit(ch)) f=ch=='-'?-1:1, ch=getchar();
    while(isdigit(ch)) x=x*10+ch-48, ch=getchar();
    x=f*x;
}

template<typename... Args>
void rd(Args&... args) {
    std::initializer_list<int>{(read(args), 0)...};
}


void init() { 
    //     M.reserve(1024); M.max_load_factor(0.25);
}

void solve() {
    int n;
    std::string s;
    std::cin >> n >> s;
    int len = s.size();
    // Ensure n is within the bounds of the string length
    n = n % len;
    // Create a substring of the last n characters
    std::string t = s.substr(len - n, n);
    // Erase the last n characters from s
    s.erase(len - n, n);
    // Prepend the substring t to s
    s = t + s;
    // Output the modified string
    std::cout << s;
}

int main() {
    init();
    #if multicase
    int _; cin>>_; while(_--) solve(); 
    #else
    solve();
    #endif
}

// Fenwick tree
int t[N];
void add(int x,int v){for(;x<N;x+=x&-x)t[x]+=v;}
int ask(int x,int a=0){for(;x;x^=x&-x)a+=t[x]; return a;}

// Math
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll qp(ll b,int t,ll a=1){for(;t;t>>=1,b=b*b%mod)if(t&1)a=a*b%mod; return a;}
int inv(ll x){return qp(x,mod-2);}

// Joint Set
int f[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}