HDU2087,1686 KMP

꽃무늬 오리포
이 두 문제는 모두 한 문자열 중의 다른 문자열의 수량을 통계한 것이다. 단지 한 문제는 중첩할 수 있고 다른 문제는 중첩할 수 없다.
코드에 입력 형식, 즉 하나의 문장의 차이를 냈는데 사실은 텍스트 문자열과 패턴 문자열이 일치하는 하위 문자열을 찾은 후에 패턴 문자열에서 시작하는 차이점을 다시 찾는 것이다.
첫 번째 AC 코드:

/*
 * @Author: hesorchen
 * @Date: 2020-07-02 22:19:34
 * @LastEditTime: 2020-07-11 12:49:56
 * @Description: https://hesorchen.github.io/
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define endl '
'
#define PI acos(-1)
#define PB push_back
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000007
#define pll pair
#define lowbit(abcd) (abcd & (-abcd))
#define max(a, b) ((a > b) ? (a) : (b))
#define min(a, b) ((a < b) ? (a) : (b))

#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define FRE                              \
    {                                    \
        freopen("in.txt", "r", stdin);   \
        freopen("out.txt", "w", stdout); \
    }

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
//==============================================================================

ll nxt[1000010];
char a[1000010], b[1000010];

void get_nxt()
{
    ll lenb = strlen(b);
    int j = 0, k = -1;
    nxt[0] = -1;
    while (j < lenb)
    {
        if (k == -1 || b[j] == b[k])
            nxt[++j] = ++k;
        else
            k = nxt[k];
    }
}
int KMP()
{
    ll lenb = strlen(b), lena = strlen(a), res = 0;
    get_nxt();
    ll i = 0, j = 0;
    while (i < lena)
    {
        if (j == -1 || a[i] == b[j])
            i++, j++;
        else
            j = nxt[j];
        if (j == lenb)
        {
            res++;
            //      
            // j = nxt[j];
            j = 0;
        }
    }
    return res;
}

int main()
{
    IOS;
    ll n;
    while (cin >> a)
    {
        if (a[0] == '#')
            break;
        cin >> b;
        cout << KMP() << endl;
    }
    return 0;
}
/*
ababa
aba
*/

두 번째 AC 코드:

/*
 * @Author: hesorchen
 * @Date: 2020-07-02 22:19:34
 * @LastEditTime: 2020-07-11 12:58:25
 * @Description: https://hesorchen.github.io/
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define endl '
'
#define PI acos(-1)
#define PB push_back
#define ll long long
#define INF 0x3f3f3f3f
#define mod 1000000007
#define pll pair
#define lowbit(abcd) (abcd & (-abcd))
#define max(a, b) ((a > b) ? (a) : (b))
#define min(a, b) ((a < b) ? (a) : (b))

#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define FRE                              \
    {                                    \
        freopen("in.txt", "r", stdin);   \
        freopen("out.txt", "w", stdout); \
    }

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
//==============================================================================

ll nxt[1000010];
char a[1000010], b[1000010];

void get_nxt()
{
    ll lenb = strlen(b);
    int j = 0, k = -1;
    nxt[0] = -1;
    while (j < lenb)
    {
        if (k == -1 || b[j] == b[k])
            nxt[++j] = ++k;
        else
            k = nxt[k];
    }
}
int KMP()
{
    ll lenb = strlen(b), lena = strlen(a), res = 0;
    get_nxt();
    ll i = 0, j = 0;
    while (i < lena)
    {
        if (j == -1 || a[i] == b[j])
            i++, j++;
        else
            j = nxt[j];
        if (j == lenb)
        {
            res++;
            //      
            j = nxt[j];
            // j = 0;
        }
    }
    return res;
}

int main()
{
    IOS;
    ll n;
    cin >> n;
    while (n--)
    {
        if (a[0] == '#')
            break;
        cin >> b >> a;
        cout << KMP() << endl;
    }
    return 0;
}
/*
ababa
aba
*/

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Git에서 개발 환경을 정리해 보았습니다.

로컬에 작업 디렉토리 만들기 mkdir [ワーキングディレクトリ名] 작업 디렉토리로 이동 cd [ワーキングディレクトリ名] 작업 디렉토리 초기화 git init git로 연결할 원격 리포지토리를 만듭니다. 이 때 REA...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU2087,1686 KMP

좋은 웹페이지 즐겨찾기