链接:

题意:

第一题来啦。

现在给你一个字符串，请问在该字符串末尾最少添加多少个字符，可以让这个字符串获得重复循环序列。

思路:

考虑一个用字符串长度为len, 并且是由长度为l的子串循环组成.

我们有S[0,len-l-1] = S[l, len], 在循环次数大于2的时候,

所以len - Next[len] 就是最小循环节的长度.

画画图就好懂了.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

//#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

#include <string>

#include <assert.h>

#include <iomanip>

#include <iostream>

#include <sstream>

#define MINF 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int MAXN = 1e6+10;

int Next[MAXN];

string s, p;

void GetNext()

{

    int len = p.length();

    Next[0] = -1;

    int j = 0;

    int k = -1;

    while (j < len)

    {

        if (k == -1 || p[k] == p[j])

        {

            ++k;

            ++j;

            Next[j] = k;

        }

        else

            k = Next[k];

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int t;

    cin >> t;

    while (t--)

    {

        cin >> p;

        GetNext();

        int len = p.length()-Next[p.length()];

        if (len != p.length() && p.length()%len == 0)

            cout << 0 << endl;

        else

            cout << len-(p.length()%len) << endl;

    }

    return 0;

}

巴特西

HDU-3746-Cyclic nacklace(KMP, 循环节)

链接:

题意:

思路:

代码:

最新文章

热门文章