1 条题解

  • 0
    @ 2017-10-15 23:21:00
    //简单Sunday算法
    //参考资料https://www.61mon.com/index.php/archives/213/
    #include <bits/stdc++.h>
     using namespace std;
    
    const int MAX_CHAR = 256;
    const int MAX_LENGTH = 1000;
    
    void GetNext(string & p, int m, int next[])
    {
        for(int i = 0; i < MAX_CHAR; i++)
            next[i] = -1;
        for(int i = 0; i < m; i++)
            next[p[i]] = i;
    } 
    
    void Sunday(string & s, int n, string & p, int m)
    {
        int next[MAX_CHAR];
        GetNext(p, m, next);
        int i = 0, j, k;
        while(i <= n - m)
        {
            j = i;
            k = 0;
            while(j < n && k < m && s[j] == p[k])
                j++, k++;
            if(k == m)
                cout << i+m << endl;
            if(i + m < n)
                i += (m - next[s[i + m]]);
            else
                return ;
        }
    }
     
    int main()
    {
        string s, p;
        int n, m;
        while(cin >> s >> p)
        {
            n = s.size();
            m = p.size();
            Sunday(s, n, p, m);
            cout << endl;
        }
        return 0;
    }
    
    
  • 1

信息

难度
9
分类
字符串 | KMP 点击显示
标签
递交数
15
已通过
3
通过率
20%
上传者