Map<Node, LCSNodeStatus> statuses = new HashMap<Node, LCSNodeStatus>();
getLCSNodeStatus(suffixTree.getRootNode(), 0, statuses);
private LCSNodeStatus getLCSNodeStatus(Node node, int height, Map<Node, LCSNodeStatus> statuses) {
LCSNodeStatus nodeStatus = new LCSNodeStatus(node, height);
if (node.getEdges().size() == 0) {
return nodeStatus;
}
for (Edge edge : node.getEdges()) {
LCSNodeStatus status = getLCSNodeStatus(edge.getEndNode(),
height + getEdgeHeightForNodeStatus(edge), statuses);
status.addString(getEdgeStringNumber(edge));
nodeStatus.mergeStatus(status);
}
statuses.put(node, nodeStatus);
return nodeStatus;
}
private CommonSubstr getLcs(int beginIndexes[], int endIndexes[], Map<Node, LCSNodeStatus> statuses) {
int max = 0;
int foundBeginIndexes[] = null;
for (LCSNodeStatus status : statuses.values()) {
if ((status.getHeight() > 0) && (status.isAllStrings()) && (max <= status.getHeight())) {
Node node = status.getNode();
int workingBeginIndexes[] = initFoundBeginIndexes();
updateFoundBeginIndexes(beginIndexes, endIndexes, node, status.getHeight(),
statuses, workingBeginIndexes);
if (verifyFoundBeginIndexes(workingBeginIndexes)) {
foundBeginIndexes = workingBeginIndexes;
max = status.getHeight();
}
}
}
if (foundBeginIndexes == null)
return null;
return new CommonSubstr(foundBeginIndexes, max);
}
private int[] initFoundBeginIndexes() {
int beginIndexes[] = new int[texts.length];
for(int i=0; i<texts.length; i++)
beginIndexes[i] = Integer.MAX_VALUE;
return beginIndexes;
}
private void updateFoundBeginIndexes(int beginIndexes[], int endIndexes[], Node node, int height,
Map<Node, LCSNodeStatus> statuses, int[] foundBeginIndexes) {
for (Edge edge : node.getEdges()) {
LCSNodeStatus nodeStatus = statuses.get(edge.getEndNode());
if ((nodeStatus != null) && nodeStatus.isAllStrings()) {
updateFoundBeginIndexes(beginIndexes, endIndexes, edge.getEndNode(),
height + getEdgeHeight(edge), statuses, foundBeginIndexes);
} else {
int stringNumber = getEdgeStringNumber(edge);
int beginIndex = edge.getBeginIndex() - height;
if ((beginIndex < endIndexes[stringNumber]) &&
(beginIndex >= beginIndexes[stringNumber]) &&
(foundBeginIndexes[stringNumber] > beginIndex)) {
foundBeginIndexes[stringNumber] = beginIndex;
}
}
}
}
private boolean verifyFoundBeginIndexes(int[] beginIndexes) {
for(int i=0; i<texts.length; i++)
if (beginIndexes[i] == Integer.MAX_VALUE)
return false;
return true;
}
private List<CommonSubstr> diff(int beginIndexes[], int endIndexes[], Map<Node, LCSNodeStatus> statuses) {
CommonSubstr commonSubstr = getLcs(beginIndexes, endIndexes, statuses);
if (commonSubstr == null)
return new LinkedList<CommonSubstr>();
List<CommonSubstr> prev = diff(beginIndexes, commonSubstr.beginIndexes, statuses);
List<CommonSubstr> next = diff(incIndexes(commonSubstr.endIndexes), endIndexes, statuses);
prev.add(commonSubstr);
if (next != null)
prev.addAll(next);
return prev;
}
public class GeneralizedSuffixTree {
// SOH - START OF HEADING
public static final char TERMINATOR1 = '\u0001';
// STX - START OF TEXT
public static final char TERMINATOR2 = '\u0002';
private String texts[];
private char terminators[];
private String generalized;
private SuffixTree suffixTree;
public GeneralizedSuffixTree(String text1, String text2) {
this(text1, text2, TERMINATOR1, TERMINATOR2);
}
public GeneralizedSuffixTree(String text1, String text2, char terminator1, char terminator2) {
this(new String[]{text1, text2}, new char[]{terminator1, terminator2});
}
public GeneralizedSuffixTree(String texts[], char terminators[]) {
this.texts = texts;
this.terminators = terminators;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < texts.length; i++) {
sb.append(texts[i]);
sb.append(terminators[i]);
}
generalized = sb.toString();
suffixTree = new SuffixTree(generalized);
fixSpanSuffixes(suffixTree.getRootNode());
}
private void fixSpanSuffixes(Node node) {
for (Edge edge : node.getEdges()) {
for (int i = 0; i < texts.length; i++) {
if ((edge.getBeginIndex() <= getGeneralizedSubstringLength(i)) &&
(edge.getEndIndex() > getGeneralizedSubstringLength(i))) {
edge.setEndIndex(getGeneralizedSubstringLength(i));
continue;
}
}
fixSpanSuffixes(edge.getEndNode());
}
}
private int getGeneralizedSubstringLength(int n) {
int length = 0;
for (int i = 0; i <= n; i++) {
length += texts[i].length() + 1;
}
return length - 1;
}
}
public boolean contains(String str) { return indexOf(str) >= 0; } public int indexOf(String str) { if (str.length() == 0) return -1; int index = -1; Node node = root; int i = 0; while (i<str.length()) { if ((node == null) || (i == text.length())) return -1; Edge edge = node.findEdge(str.charAt(i)); if (edge == null) return -1; index = edge.getBeginIndex()-i; i++; for(int j=edge.getBeginIndex()+1; j<=edge.getEndIndex(); j++) { if (i == str.length()) break; if (text.charAt(j) != str.charAt(i)) return -1; i++; } node = edge.getEndNode(); } return index; }
SELECT 'log message' AS 'title';
DELIMITER $$
-- PROCEDURE pLog
-- outputs log message
-- Params:
-- sTitle - title
-- sMsg - log message
DROP PROCEDURE IF EXISTS `pLog` $$
CREATE PROCEDURE `pLog`(IN sTitle VARCHAR(255), IN sMsg VARCHAR(255))
BEGIN
DECLARE strSQL VARCHAR(512);
SET strSQL = CONCAT('SELECT ''', sMsg, ''' AS ''', sTitle, '''');
CALL pExecuteImmediate(strSQL);
END $$
-- PROCEDURE pExecuteImmediate
-- executes dynamic SQL statement
-- Params:
-- tSQLStmt - SQL statement to be executed
DROP PROCEDURE IF EXISTS `pExecuteImmediate` $$
CREATE PROCEDURE `pExecuteImmediate`(IN tSQLStmt TEXT)
BEGIN
SET @executeImmediateSQL = tSQLStmt;
PREPARE executeImmediateSTML FROM @executeImmediateSQL;
EXECUTE executeImmediateSTML;
DEALLOCATE PREPARE executeImmediateSTML;
END $$
DELIMITER ;
DELIMITER $$
-- FUNCTION pCheckCurrentUserRoot
-- checks if we are connected as root user
DROP PROCEDURE IF EXISTS `pCheckCurrentUserRoot` $$
CREATE PROCEDURE `pCheckCurrentUserRoot`()
BEGIN
DECLARE strUser VARCHAR(50);
CALL pLog('INFO', 'pCheckCurrentUserRoot...');
SELECT USER() INTO strUser;
CALL pLog('INFO', CONCAT('user: ', strUser));
IF (strUser LIKE 'root%') THEN
CALL pLog('INFO', 'current user is root');
ELSE
CALL pLog('INFO', 'current user is not root');
END IF;
END $$
DELIMITER ;
Edge Start End Suf First Last String 1 0 1 -1 0 3 book 3 0 3 0 1 1 o 5 0 5 -1 3 3 k 2 3 2 -1 2 3 ok 4 3 4 -1 3 3 k
Edge Start End Suf First Last String 8 0 8 -1 5 5 e 1 0 1 -1 0 5 bookke 3 0 3 0 1 1 o 6 0 6 0 3 3 k 2 3 2 -1 2 5 okke 4 3 4 -1 3 5 kke 7 6 7 -1 5 5 e 5 6 5 -1 4 5 ke
Edge Start End Suf First Last String 3 0 3 5 0 1 ca 5 0 5 0 1 1 a 7 0 7 -1 4 4 o 1 3 1 -1 2 4 cao 4 3 4 -1 4 4 o 2 5 2 -1 2 4 cao 6 5 6 -1 4 4 o
Edge Start End Suf First Last String 5 0 5 3 0 1 go 3 0 3 0 1 1 o 8 0 8 -1 5 5 l 1 5 1 -1 2 5 ogol 6 5 6 -1 5 5 l 4 3 4 -1 3 5 gol 2 3 2 -1 2 5 ogol 7 3 7 -1 5 5 l
Edge Start End Suf First Last String 9 0 9 0 1 1 b 11 0 11 -1 6 6 c 7 0 7 9 0 1 ab 10 9 10 -1 6 6 c 5 9 5 7 2 3 ab 8 7 8 -1 6 6 c 3 7 3 5 2 3 ab 6 5 6 -1 6 6 c 2 5 2 -1 4 6 abc 4 3 4 -1 6 6 c 1 3 1 -1 4 6 abc
mvn test ... ------------------------------------------------------- T E S T S ------------------------------------------------------- Running com.blogspot.illyakeeplearning.suffixtree.SuffixTreeTest Start End Suf First Last String 0 5 0 1 1 a 0 3 5 0 1 ca 0 7 -1 4 4 o 3 1 -1 2 4 cao 3 4 -1 4 4 o 5 2 -1 2 4 cao 5 6 -1 4 4 o Suffix : acao comparing: acao to acao Suffix : ao comparing: ao to ao Suffix : cacao comparing: cacao to cacao Suffix : cao comparing: cao to cao Suffix : o comparing: o to o All Suffixes present! Leaf count : 5 OK Branch count : 7 OK Tests run: 1, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.032 sec Results : Tests run: 1, Failures: 0, Errors: 0, Skipped: 0
Posts
All Comments
