hdu 6863 Isomorphic Strings hash + common factor

Meaning:

t group input, each group of data input an integer n, representing the length of the string. Next, enter another string

You need to judge whether the string can be divided into more than 1 segment, and the minimum representation of these segments is the same

For example: abccab, which can be divided into two segments, abc and cab. They both use the minimum representation (that is, the minimum representation of dictionary order) to represent abc, so the two strings are the same

 

Solution:

Because you need to divide the string into several segments. Suppose it is divided into x segments, then x must satisfy n%x==0

 

There are two methods here. The first is to enumerate the factor of n, and then judge whether this factor is OK or not

The other is: if there is a factor X that can meet the meaning of the question (that is, the length of a paragraph is x, and each paragraph is equal), then it is divided into n/x segments, and the number of each letter in each paragraph must remain the same

Then we can find the maximum common factor of the number of letters, set it as ans, and then enumerate it in 1-ans. This is less complex than the factor of de violence enumeration n

 

How do we judge whether a factor x can be unsatisfied?

For a string abccab, we can find that the number of letters a, b and c is 2, so the greatest common factor between them and n is 2

Then the string with length n can be divided into 2 segments at most, and the length of each segment is n/2

Then we start to enumerate the factors in the interval [1,2). First, we need to judge that n%x==0, which is not equal to 0

This enumeration is to merge several n/2, for example, 1 satisfies n%x==0

At this time, abc is a segment and cab is a segment (if x==2, then two n/2 are combined into one segment, that is, abccab is a segment. Because the topic requires that the strings must be separated, 2 is not allowed)

For the first abc segment, we first mark the hash value of abc, then mark the hash value of bca, and then mark the hash value of cab

Then judge whether the hash value of the following segment has been marked. If it has been marked, it will be fine. If it has not been marked, it will prove that this factor is not good

 

code:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int blo=13331;
const int maxn = 5e6+5;
ll xp[maxn],hash_1[maxn],num[maxn];
map<ll,ll>r;
void init()
{
    xp[0]=1;
    for(ll i=1; i<maxn; i++)
        xp[i]=xp[i-1]*blo;
}
ll make_hash(char str[],ll hash_[],ll len)
{
    hash_[0]=0;
    for(ll i=1; i<=len; i++)
    {
        hash_[i]=hash_[i-1]*blo+(str[i]-'a'+1);
        //cout<<hash_[i]<<" ";
    }
    return len;
}
char str[maxn];
int main()
{

    init();
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        //r.clear();
        ll n,flag=1;
        scanf("%lld",&n);
        scanf("%s",str+1);
        make_hash(str,hash_1,n);
        memset(num,0,sizeof(num));
        for(ll i=1;i<=n;++i)
        {
            num[str[i]-96]++;
        }
        ll ans=n;
        for(ll i=1;i<=26;++i)  //If the minimum representation of each string is the same after grouping, the number of each letter is the same, so we can
        {           //To start with
            if(num[i])
            ans=__gcd(ans,num[i]);  //this ans What's in it is the maximum number of groups you can be divided into
        }
        ll u=n/ans;  //According to the maximum score ans Groups, length of each group
        if(u==1 && n!=1)
        {
            flag=0;
        }
        else
        {
            for(ll k=1;k<ans;++k)  //Enumeration judgment
            {
                ll len=k*u;
                if(n%len)
                {
                    continue;
                }
                r.clear();
                flag=0;
                ll temp=hash_1[len]-hash_1[0]*xp[len];
                r[temp]=1;
                for(ll i=1;i<=len;++i)  //The hash values of various types of strings of a string are calculated and marked
                { //For example, string abc,You don't just have to figure it out abc And calculate the hash value of bca,cab Hash value of
                    temp=temp*blo+(str[i]-96);
                    r[temp-hash_1[i]*xp[len]]=1;
                }
                for(ll j = 1; j * len <= n; j++)  //Determine whether the latter groups are the same as the first group
                {

                    if(r[hash_1[j*len]-hash_1[(j - 1)*len]*xp[len]]==0)
                    {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0)
                {

                    break;
                }
            }
        }
        if(!flag)
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

 

Tags: Hash Algorithm

Posted by colinexl on Mon, 23 May 2022 13:40:28 +0300