12361.cpp

//11512
//GATTACA
//Misc;String Matching;Suffix Array;Longest Common Prefix
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <sstream>
#include <cmath>
#include <set>
#include <stack>
#define MAX 600200
#define ull unsigned long long
using namespace std;

struct Item {
    ull v; int p;
    Item(ull v, int p) : v(v), p(p) { }
};

int RA[MAX], tempRA[MAX];
int SA[MAX], tempSA[MAX];
int C[MAX];                
int Phi[MAX], PLCP[MAX], LCP[MAX];
int IDX[MAX];
set<string> Q;
set<ull> R;

void suffix_sort(int n, int k) {
    memset(C, 0, sizeof C);        

    for (int i = 0; i < n; i++)        
        C[i + k < n ? RA[i + k] : 0]++;
        
    int sum = 0;
    for (int i = 0; i < max(256, n); i++) {                     
        int t = C[i]; 
        C[i] = sum; 
        sum += t;
    }

    for (int i = 0; i < n; i++)        
        tempSA[C[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i];

    memcpy(SA, tempSA, n*sizeof(int));
}

void suffix_array(string &s) {             
    int n = s.size();
    
    for (int i = 0; i < n; i++) 
        RA[i] = s[i] - 1;              

    for (int i = 0; i < n; i++) 
        SA[i] = i;

    for (int k = 1; k < n; k *= 2) {     
        suffix_sort(n, k);
        suffix_sort(n, 0);

        int r = tempRA[SA[0]] = 0;
        for (int i = 1; i < n; i++) {
            int s1 = SA[i], s2 = SA[i-1];
            bool equal = true;
            equal &= RA[s1] == RA[s2];
            equal &= RA[s1+k] == RA[s2+k];
            
            tempRA[SA[i]] = equal ? r : ++r;     
        }
                
        memcpy(RA, tempRA, n*sizeof(int));
    } 
}

void lcp(string &s) {
    int n = s.size();

    Phi[SA[0]] = -1;         
    for (int i = 1; i < n; i++)  
        Phi[SA[i]] = SA[i-1];  
    
    int L = 0;
    for (int i = 0; i < n; i++) {
        if (Phi[i] == -1) { 
            PLCP[i] = 0; 
            continue; 
        }
        while (s[i + L] != '\1' && s[i + L] == s[Phi[i] + L]) 
            L++;

        PLCP[i] = L;
        L = max(L-1, 0);                      
    }
    
    for (int i = 1; i < n; i++)                 
        LCP[i] = PLCP[SA[i]];
}

bool isPrefix(string& left, string& right) {
    if (right.size() < left.size()) return false;
    for(int i=0; i<left.size(); i++) {
        if (right[i] != left[i]) return false;
    }
    return true;
}

int main() {
    int n;
    while(cin >> n, n) {
        Q.clear();
        R.clear();
        
        for(int i=0; i<n; i++) {
            string temp; cin >> temp;
            Q.insert(temp);
        }

        stringstream ss;
        int k = 0, kk = 0;

        string last = "$";
        for(set<string>::iterator it = Q.begin(); it!=Q.end(); it++) {
            string current = *it;
            
            IDX[k++] = ++kk;
            for(int i=0; i<it->size(); i++)
                IDX[k++] = kk;

            ss << current << '\1';               
            
            if (isPrefix(last, current))
                R.erase(1ull << kk-1);

            R.insert(1ull << kk);

            last = current;
        }

        string s = ss.str();

        suffix_array(s);
        lcp(s);
        
        stack<Item> ST;
        
        for(int i=0; i<s.size(); i++) {
            while(!ST.empty() && ST.top().p > LCP[i]) {
                Item item = ST.top(); ST.pop();
                R.insert(item.v);
                if (!ST.empty())
                    ST.top().v |= item.v;
            }

            if (LCP[i]) {
                if (ST.empty() || LCP[i] > ST.top().p) {
                    Item item((1ull << IDX[SA[i]]) | (1ull << IDX[SA[i-1]]), LCP[i]);
                    ST.push(item);
                } else if (LCP[i] == ST.top().p) {
                    ST.top().v |= 1ull << IDX[SA[i]];   
                } 
            }
        }
        while(!ST.empty()) {
            Item item = ST.top(); ST.pop();
            R.insert(item.v);
            if (!ST.empty())
                ST.top().v |= item.v;
        }
        
        cout << R.size() << endl;
   }
}