Skip to content

Instantly share code, notes, and snippets.

@juanplopes

juanplopes/12361.cpp

Forked from anonymous/12361.cpp
Created Oct 31, 2012
Embed
What would you like to do?
//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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.