Submission #818183

#	Time	Username	Problem	Language	Result	Execution time	Memory
818183		vjudge1	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	1 ms	212 KiB

necklace

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int maxn=100;
string s;
int z[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--)
    {
        cin >> s;
        int n=s.size();
        s=' '+s;
        fill(z, z+n+1, 0);
        for (int i=2, l=1, r=1; i<=n; ++i)
        {
            if (i<=r)
                z[i]=min(r-i+1, z[i-l+1]);
            while (i+z[i]<=n && s[z[i]+1]==s[i+z[i]])
                ++z[i];
            if  (i+z[i]-1>r)
                l=1, r=i+z[i]-1;
        }
        int ans=0;
        for (int i=1, c=1; i<=n; ++i)
        {
            if (n%i) continue;
            c=1;
            for (int j=i+1; j<=n && c; j+=i)
                if (z[j]<i) c=0;
            if (c>0)
            {
                ans=i;
                break;
            }
        }
        cout << ans << '\n';
    }
}

• Subtask 1: 0 / 15