/*
ID: noszaly1
TASK: {TASK}
LANG: C++11
*/
//Noszály Áron 11o Debreceni Fazekas Mihály Gimnázium
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#ifndef ONLINE_JUDGE
# define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
# define LOG(x) ((void)0)
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double PI=acos(-1);
template<typename T> T getint() {
T val=0;
char c;
bool neg=false;
while((c=gc()) && !(c>='0' && c<='9')) {
neg|=c=='-';
}
do {
val=(val*10)+c-'0';
} while((c=gc()) && (c>='0' && c<='9'));
return val*(neg?-1:1);
}
struct rolling_hash {
vector<ll> lst;
vector<ll> hatv;
ll p;
ll mod;
rolling_hash(string& t, ll p_, ll mod_) {
lst.resize(sz(t));
hatv.resize(sz(t));
p=p_;
mod=mod_;
ll curr=p;
lst[0]=t[0]%mod;
hatv[0]=1;
for(int i=1;i<sz(t);++i) {
lst[i]=(lst[i-1]+curr*t[i])%mod;
hatv[i]=curr;
curr=(curr*p)%mod;
}
}
ll base_hash_fast(ll l, ll r) {
ll hsh=(lst[r]-(l>0?lst[l-1]:0)+mod); //ez most p^l-es, tehát sz(lst)-l-1-el kell megszoroznunk
return (hsh*hatv[sz(lst)-l-1])%mod;
}
bool probably_equal(ll l1, ll r1, ll l2, ll r2) {
if(r1-l1!=r2-l2) return false;
if(l1>l2) {
swap(l1, l2);
swap(r1, r2);
}
ll egyik=(lst[r2]-(l2>0?lst[l2-1]:0)+mod), masik=(lst[r1]-(l1>0?lst[l1-1]:0)+mod);
return (egyik-(masik*hatv[l2-l1]))%mod==0; //WATCH OUT FOR THIS KIND OF ERROR!!
}
};
ll p1=19, mod1=1e9+7;
ll p2=31, mod2=1000000409;
int n,k;
string t[501];
int szum[501][501][26];
int main() {
IO;
cin>>n>>k;
vector<rolling_hash> hsh1, hsh2;
for(int i=0;i<n;++i) {
cin>>t[i];
hsh1.push_back(rolling_hash(t[i], p1, mod1));
hsh2.push_back(rolling_hash(t[i], p2, mod2));
}
for(int i=0;i<n;++i) {
for(int j=0;j<n;++j) {
szum[i][j][t[i][j]-'a']++;
if(j>0) {
for(int k=0;k<26;++k) {
szum[i][j][k]+=szum[i][j-1][k];
}
}
}
}
bool ans=false;
for(int i=0;i<n&&!ans;++i) {
for(int j=i+1;j<n&&!ans;++j) {
//bináris keresés, hogy meddig egyenlőek
int L=-1, R=n;
if(t[i][0]==t[j][0]) {
L++;
for(int k=10;k>=0;k--) {
int akt=L+(1<<k);
if(akt<n) {
if(hsh1[i].base_hash_fast(0,akt)==hsh1[j].base_hash_fast(0,akt)&&
hsh2[i].base_hash_fast(0,akt)==hsh2[j].base_hash_fast(0,akt)){
L=akt;
}
}
}
}
if(t[i][n-1]==t[j][n-1]) {
R--;
for(int k=10;k>=0;k--) {
int akt=R-(1<<k);
if(akt>=0) {
if(hsh1[i].base_hash_fast(akt,n-1)==hsh1[j].base_hash_fast(akt,n-1)&&
hsh2[i].base_hash_fast(akt,n-1)==hsh2[j].base_hash_fast(akt,n-1)){
R=akt;
}
}
}
}
if(R==0 && L==n-1) {
ans=true;
break ;
}
assert(L<R);
bool ok=true;
for(int l=0;ok&&l<26;++l) {
ok&=(szum[i][R-1][l]-(L>=0?szum[i][L][l]:0))==(szum[j][R-1][l]-(L>=0?szum[j][L][l]:0));
}
if(ok && R-L-1<=k) ans|=true;
}
}
cout<<(ans?"DA":"NE")<<"\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
6552 KB |
Output is correct |
2 |
Correct |
14 ms |
6648 KB |
Output is correct |
3 |
Correct |
18 ms |
6520 KB |
Output is correct |
4 |
Correct |
9 ms |
6520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
6520 KB |
Output is correct |
2 |
Correct |
11 ms |
6620 KB |
Output is correct |
3 |
Correct |
11 ms |
6520 KB |
Output is correct |
4 |
Correct |
16 ms |
6520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
6520 KB |
Output is correct |
2 |
Correct |
17 ms |
6576 KB |
Output is correct |
3 |
Correct |
16 ms |
6520 KB |
Output is correct |
4 |
Correct |
10 ms |
6520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
6616 KB |
Output is correct |
2 |
Correct |
9 ms |
6520 KB |
Output is correct |
3 |
Correct |
10 ms |
6620 KB |
Output is correct |
4 |
Correct |
16 ms |
6520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
34012 KB |
Output is correct |
2 |
Correct |
55 ms |
33984 KB |
Output is correct |
3 |
Correct |
95 ms |
33996 KB |
Output is correct |
4 |
Correct |
51 ms |
34004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
33996 KB |
Output is correct |
2 |
Correct |
48 ms |
34040 KB |
Output is correct |
3 |
Correct |
52 ms |
34040 KB |
Output is correct |
4 |
Correct |
122 ms |
34076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
57 ms |
34040 KB |
Output is correct |
2 |
Correct |
58 ms |
33992 KB |
Output is correct |
3 |
Correct |
110 ms |
34080 KB |
Output is correct |
4 |
Correct |
51 ms |
34040 KB |
Output is correct |