1 条题解

  • 0
    @ 2023-3-25 17:02:46
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    string t, p;
    int nxt[1000 * 2 + 1 + 5];
    void getNxt(const string &s)
    {
        nxt[0] = 0;
        for (int i = 1; i < s.length(); i++)
        {
            int j = nxt[i - 1];
            while (j != 0 && s[j] != s[i])
                j = nxt[j - 1];
            if (s[j] == s[i])
                j++;
            nxt[i] = j;
        }
    }
    signed main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        while (cin >> t)
        {
            if (t == "#")
                break;
            cin >> p;
            // 计算 t 里面能裁出来多少个 p
            string s = p + " " + t;
            getNxt(s);
            // t 的位置为第 p.length()+2 个字符
            int now = p.length() + 1; // t第一个字符在s中的下标
            int ans = 0;
            while (now < s.length())
            {
                if (nxt[now] == p.length())
                {
                    ans++;
                    now += p.length();
                }
                else
                    now++;
            }
            cout << ans << "\n";
        }
        return 0;
    }
    
    • 1

    信息

    ID
    685
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    48
    已通过
    19
    上传者