Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

LA 5794

Solução: Lucas Castro

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <set>

using namespace std;

typedef long long int ll;

#define MAXN 70
#define MAXC 10010
#define INF 0x3f3f3f3f
#define N MAXN*MAXC

int n;
int sz[MAXN];
ll who[MAXN*MAXC];


char str[N], inp[N];
int H, Bucket[N], nBucket[N], Rank[N], Height[N], c;

typedef pair<int,ll> ill;

struct Suffix {
  int idx; // Suffix starts at idx, i.e. it's str[ idx .. L-1 ]
  bool operator<(const Suffix& sfx) const
  // Compares two suffixes based on their first 2H symbols,
  // assuming we know the result for H symbols.
  {
    if(H == 0) return str[idx] < str[sfx.idx];
    else if(Bucket[idx] == Bucket[sfx.idx])
      return (Bucket[idx+H] < Bucket[sfx.idx+H]);
    else
      return (Bucket[idx] < Bucket[sfx.idx]);
  }
  bool operator==(const Suffix& sfx) const {
    return !(*this < sfx) && !(sfx < *this);
  }
} Pos[N];

int UpdateBuckets(int L) {
  int start = 0, id = 0, c = 0;
  for(int i = 0; i < L; i++) {
    if(i != 0 && !(Pos[i] == Pos[i-1])) {
      start = i;
      id++;
    }
    if(i != start)
      c = 1;
    nBucket[Pos[i].idx] = id;
  }
  memcpy(Bucket, nBucket, 4 * L);
  return c;
}

void SuffixSort(int L) {
  H = 0;
  for(int i = 0; i < L; i++) Pos[i].idx = i;
  sort(Pos, Pos + L);
  c = UpdateBuckets(L);
  for(H=1;c;H *= 2) {
    // Sort based on first 2*H symbols, assuming
    // that we have sorted based on first H character
    sort(Pos, Pos+L);
    // Update Buckets based on first 2*H symbols
    c = UpdateBuckets(L);
  }
}

// Must compute the suffix array Pos first
void ComputeLCP(int L) {
  for (int i = 0; i < L; i++) Rank[Pos[i].idx] = i;
  int h = 0;
  for (int i = 0; i < L; i++)
    if (Rank[i] > 0) {
      int k = Pos[Rank[i] - 1].idx;
      while (str[i+h] == str[k+h])
        ++h;
      Height[Rank[i]] = h;
      if (h > 0) --h;
    }
}


set<ll> s;
string saux;
set<string> ss;
int len[N];

int main(){
    int m;
    int t = 49;
    while(scanf(" %d",&m) == 1 && m > 0){        
        n = 0;
        for(int i = 0 ; i < m ;i++){        
            cin >> saux;
            for(int j = 0 ; j < saux.size() ; j++){
                str[n++] = saux[j];
            }
            str[n++] = 'a' - 1 - i;
        }      
        str[n++] = '\0';    

        int last = INF;
        int k = m;
        for(int i = n - 2 ; i >= 0 ; i--){
            if(str[i] < 'a'){
                k--;
                last = i;
                continue;
            }else{
                who[i] = k;
                len[i] = last - i;                          
            }
        }

        SuffixSort(n);
        ComputeLCP(n);

        /* Pos[i].idx guarda a posicao na string original */      
        s.clear();              

        for(int i = 0 ; i < n - 1 ; i++) Height[i] = Height[i+1];        
        Height[n-1] = 0;

        vector<ill> pilha;

        for(int i = m + 1 ; i < n; i++){        
            if(Height[i] < len[Pos[i].idx] && (i == m + 1 || Height[i-1] < len[Pos[i].idx])){
                  s.insert(1LL << who[Pos[i].idx]);
            }
            ll mask = 0LL;      

            while(!pilha.empty() && Height[i] < pilha.back().first){
                mask |= pilha.back().second;                
                s.insert(mask);
                pilha.pop_back();          
            }
            if(!pilha.empty()) pilha.back().second |= mask;

            if(Height[i] == 0)  continue;          

            if(pilha.empty() || Height[i] > pilha.back().first){
                mask |= (1LL << who[Pos[i].idx]) | (1LL << who[Pos[i + 1].idx]);                
                pilha.push_back(ill(Height[i],mask));              
            }else{
                pilha.back().second |= (1LL << who[Pos[i].idx]) | (1LL << who[Pos[i + 1].idx]);
            }
        }
        printf("%d\n",s.size());
    }  

    return 0;
}