字符串匹配_C/C++/C#

字符串匹配

利用map进行跳跃（不适用于太长的子字符串）【map存不下】【拉胯】

#include 
#include 
#include 
#include 

using namespace std;
int main()
{
    int n,m;
    string s,ss;
    cin>>n>>ss;
    cin>>m>>s;
    mapmp;
    mp[ss]=-1;
    for (int i = 1; i <= n; i ++ )
    {
        ss.erase(n-i,1);
        //cout<0)
            {
                i+=(mp[sss]-1);
                break;
            }
            sss.erase(0,1);
        }
    }
}

kmp算法

#include
#include
#include
#include
#include
#include
using namespace std;
char s[2000000],p[2000000];
int kmp[2000000];
int main()
{
    int n,m;
    cin>>n;cin>>p+1;
    cin>>m;cin>>s+1;
    int k=0;
    for (int i = 2; i <= n; i ++ )
    {
        while(k&&p[i]!=p[k+1])k=kmp[k];
        if(p[i]==p[k+1])k++;
        kmp[i]=k;
    }
    k=0;
    for (int i = 1; i <= m; i ++ )
    {
        while(k&&s[i]!=p[k+1])k=kmp[k];
        if(s[i]==p[k+1])k++;
        if(k==n)
        {
            cout< 
#include 
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    //子串自我匹配
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    //举例abcab
    

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    //举例abcabcabe
    
    return 0;
} 
 
 参考：AcWing 831. KMP字符串 - AcWinghttps://www.acwing.com/activity/content/code/content/43108/

字符串匹配

C/C++/C#相关栏目本月热门文章