VO17TV – spoj

Đề bài

Thuật toán

  • (đang cập nhập)

Code

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define X first
#define Y second
#define ll long long
#define mp make_pair
#define pb push_back
#define endl '\n'
 
const int MAXN = 1e5 + 2;
const int base1 = 1e9 + 7;
const int base2 = 1e9 + 289;
const int N = 5000;
 
using namespace std;
struct data
{
    int x1,x2,id;
}dd[MAXN];
int n,k;
int len[MAXN];
ll M1[MAXN],M2[MAXN],h1[51][MAXN],h2[51][MAXN];
 
void build1(ll h[],string s,int n)
{
    FORE(i,1,n)
    h[i] = (h[i-1]*M1[1] + s[i-1])%base1;
}
 
int get1(ll h[],int l,int r)
{
    return (h[r] - h[l-1]*M1[r-l+1] + 1ll*base1*base1)%base1;
}
 
void build2(ll h[],string s,int n)
{
    FORE(i,1,n)
    h[i] = (h[i-1]*M2[1] + s[i-1])%base2;
}
 
int get2(ll h[],int l,int r)
{
    return (h[r] - h[l-1]*M2[r-l+1] + 1ll*base2*base2)%base2;
}
 
int cmp(data a,data b)
{
    if (a.x1 != b.x1) return a.x1 < b.x1;
    if (a.x2 != b.x2) return a.x2 < b.x2;
    return a.id < b.id;
}
 
int check(int r)
{
    int cnt = 0;
    FORE(i,1,n)
    {
        int rr = len[i] - r + 1;
        FORE(j,1,rr)
        {
            int x1 = get1(h1[i] , j , j + r - 1);
            int x2 = get2(h2[i] , j , j + r - 1);
            dd[++cnt].x1 = x1;
            dd[cnt].x2 = x2;
            dd[cnt].id = i;
        }
    }
    sort(dd+1,dd+cnt+1,cmp);
    int dem = 0;
    FORE(i,1,cnt)
    if (dd[i].x1 != dd[i-1].x1 || dd[i].x2 != dd[i-1].x2)
    {
        dem = 1;
    }
    else
    if (dd[i].id != dd[i-1].id)
    {
        ++dem;
        if (dem == k) return 1;
    }
    return 0;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("vo17tv.inp", "r", stdin);
    freopen("vo17tv.ans", "w", stdout);
    #endif
    M1[1] = 2802; M2[1] = 2208;
    cin>>n>>k;
    int lenmi = 0;
    FORE(i,1,n)
    {
        string st;
        cin>>st;
        len[i] = st.size();
        build1(h1[i] , st , len[i]);
        build2(h2[i] , st , len[i]);
        lenmi = max(lenmi , len[i]);
    }
    FORE(i,2,lenmi) M1[i] = M1[i-1]*M1[1]%base1;
    FORE(i,2,lenmi) M2[i] = M2[i-1]*M2[1]%base2;
    int l = 1;
    int r = lenmi;
    int ans = 0;
    while(l <= r)
    {
        int mid = (l+r)>>1;
        if (check(mid))
        {
            l = mid + 1;
            ans = mid;
        }
        else
            r = mid - 1;
    }
    cout<<ans<<endl;
    return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*