Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* TAHMID RAHMAN
- DAMIAN FOREVER
- MATH LOVER
- NEVER GIVE UP
- */
- #include<bits/stdc++.h>
- using namespace std;
- #define pi acos(-1.0)
- #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
- #define ll long long
- #define pb push_back
- #define fi first
- #define se second
- #define in insert
- #define mp make_pair
- #define GCD(a,b) __gcd(a,b);
- #define endl "\n"
- #define FRU freopen("out.txt","w",stdout)
- #define FRO freopen("in.txt","r",stdin)
- #define INFLL 9223372036854775807
- #define all(x) (x).begin(),(x).end()
- #define MAXN 100001
- #define ar array
- #define lb lower_bound
- #define ub upper_bound
- #define minpq priority_queue<ll, vector<ll>, greater<ll>>
- #define maxpq priority_queue<ll>
- const int mxN=2e5;
- const int MOD=1e9+7;
- template<typename ForwardIterator, typename T>
- ForwardIterator first_less_than (ForwardIterator first, ForwardIterator last, T value)
- {auto it = std::lower_bound (first, last, value);
- return (it == first ? last : --it);}
- bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b)
- {
- return (a.second < b.second);
- }
- #define debugxx(v) {for(auto x:v){cout<<x.fi<<" "<<x.se<<endl;}cout<<endl;}
- #define debugx(v){for(auto y:v) {cout<<y<<" ";}cout<<endl;}
- #define debug(x) cout<<#x<<" ";_print(x); cout<<endl;
- typedef unsigned long long ull;
- typedef long double lld;
- void _print(ll t) {cout << t;}
- void _print(int t) {cout << t;}
- void _print(string t) {cout << t;}
- void _print(char t) {cout << t;}
- void _print(lld t) {cout << t;}
- void _print(double t) {cout << t;}
- void _print(ull t) {cout << t;}
- template <class T, class V> void _print(pair <T, V> p);
- template <class T> void _print(vector <T> v);
- template <class T> void _print(set <T> v);
- template <class T, class V> void _print(map <T, V> v);
- template <class T> void _print(multiset <T> v);
- template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.fi); cout << ","; _print(p.se); cout << "}";}
- template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
- template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
- template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
- template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}
- //Don't hesitate to ask me if you don't understand my code.......Happy coding,Tahmid...;
- vector<ll> SortCyclicShifts(string s){
- int n=s.size();
- const int alphabet=256;
- vector<ll>Start(n),Freq(max(alphabet,n),0),EClass(n);
- for(int i=0;i<n;i++) Freq[s[i]]++;
- for(int i=1;i<alphabet;i++) Freq[i]+=Freq[i-1];
- for(int i=0;i<n;i++) Start[--Freq[s[i]]]=i;
- int Class=1;
- EClass[Start[0]]=0;
- for(int i=1;i<n;i++){
- if(s[Start[i]]!=s[Start[i-1]]) Class++;
- EClass[Start[i]]=Class-1;
- }
- for(int p=0;(1<<p)<n;p++){
- vector<ll> STemp(n),ECTemp(n);
- for(int i=0;i<n;i++){
- STemp[i]=Start[i]-(1<<p);
- if(STemp[i]<0) STemp[i]+=n;
- }
- fill(Freq.begin(),Freq.begin()+Class,0);
- for(int i=0;i<n;i++) Freq[EClass[STemp[i]]]++;
- for(int i=1;i<Class;i++) Freq[i]+=Freq[i-1];
- for(int i=n-1;i>=0;i--){
- Start[--Freq[EClass[STemp[i]]]]=STemp[i];
- }
- ECTemp[Start[0]]=0;
- Class=1;
- for(int i=1;i<n;i++){
- pair<ll,ll>prev,curr;
- prev={EClass[Start[i-1]],EClass[(Start[i-1]+(1<<p))%n]};
- curr={EClass[Start[i]],EClass[(Start[i]+(1<<p))%n]};
- if(curr!=prev) Class++;
- ECTemp[Start[i]]=Class-1;
- }
- for(int i=0;i<n;i++){
- EClass[Start[i]]=ECTemp[Start[i]];
- }
- }
- return Start;
- }
- vector<ll> BuildSuffixArray(string s){
- s+='$';
- vector<ll>ret=SortCyclicShifts(s);
- ret.erase(ret.begin());
- return ret;
- }
- vector<ll> lcp(vector<ll>&sa,string &s)
- {
- ll n=sa.size();
- vector<ll>ranks(n);
- ll h=0,i=0;
- s+='$';
- vector<ll>l(n,0);
- for(i=0;i<n;i++)
- ranks[sa[i]]=i;
- for(i=0;i<n;i++)
- {
- if(ranks[i]>0)
- {
- ll k=sa[ranks[i]-1];
- while(s[i+h]==s[k+h]){
- h++;
- }
- l[ranks[i]]=h;
- if(h)
- h--;
- }
- }
- return l;
- }
- ll lcp(ll a,ll b,vector<ll>&v)
- {
- ll i=a+1;
- ll ans=v[i];
- for(i=a+1;i<=b;i++)
- {
- ans=min(ans,v[i]);
- }
- return ans;
- }
- int main()
- {
- fastio;
- ll t;
- //t=1;
- cin>>t;
- while(t--)
- {
- ll n,i,j,k;
- cin>>n;
- map<ll,ll>m;
- string s1,s;
- for(i=0;i<n;i++)
- {
- cin>>s;
- s1+=s;
- s1+='0'+i;
- }
- s1.pop_back();
- if(n==1)
- {
- cout<<s1<<endl;
- continue;
- }
- ll temp=0;
- for(i=0;i<s1.size();i++)
- {
- if(s1[i]>='a'&&s[i]<='z')
- {
- m[i]=temp;
- }
- else
- {
- temp++;
- m[i]=temp;
- }
- }
- vector<ll>sa=BuildSuffixArray(s1);
- vector<ll>lc=lcp(sa,s1);
- ll l=0,r=1;
- ll ans=1;
- // debug(n);
- //debug(sa);
- multiset<ll>st;
- st.in(m[sa[0]]);
- st.in(m[sa[1]]);
- while(r<sa.size())
- {
- set<ll>y;
- for(auto x:st )
- {
- y.in(x);
- }
- if(y.size()==n)
- {
- ll val=lcp(l,r,lc);
- ans=max(ans,val);
- st.erase(m[sa[l]]);
- l++;
- if(l<sa.size())
- st.in(m[sa[l]]);
- else
- break;
- }
- else
- {
- r++;
- if(r<sa.size())
- st.in(m[sa[r]]);
- }
- }
- cout<<ans<<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement