/*
This code relates to the following DBA.StackExchange answer:
http://dba.stackexchange.com/questions/131759/is-there-a-sql-server-implementation-of-the-longest-common-substring-problem/131766#131766
A T-SQL installation script (no external DLL) containing only this User-Defined Aggregate (UDA) is located at:
http://pastebin.com/wnLwT1GM
Date: 2016-03-16
Version: 1.0.3
Copyright (c) 2016 Sql Quantum Leap. All rights reserved.
http://www.SqlQuantumLeap.com
*/
using System;
using System.Collections.Generic;
using System.Data.SqlTypes;
using System.IO;
using System.Xml;
using Microsoft.SqlServer.Server;
[Serializable]
[Microsoft.SqlServer.Server.SqlUserDefinedAggregate(Format.UserDefined,
IsInvariantToDuplicates = true, IsInvariantToNulls = true, IsInvariantToOrder = true,
IsNullIfEmpty = false, MaxByteSize = -1)]
public struct LongestCommonSubstring : IBinarySerialize
{
private bool _IsEmpty;
private string _TempFirstValue;
private bool _IsFirstComparison;
private List<string> _Matches;
private bool _HasMerged;
private bool? _ReturnAllSubstrings;
public void Init()
{
_IsEmpty = false;
_TempFirstValue = String.Empty;
_IsFirstComparison = true;
_Matches = new List<string>();
_HasMerged = false;
_ReturnAllSubstrings = null;
return;
}
public void Accumulate([SqlFacet(MaxSize = 4000)] SqlString SomeString, SqlBoolean ReturnAllSubstrings)
{
// grab option on first call only to avoid potential "odd" behavior
if (!_ReturnAllSubstrings.HasValue)
{
if (ReturnAllSubstrings.IsTrue)
{
_ReturnAllSubstrings = true;
}
else
{
_ReturnAllSubstrings = false;
}
}
if (SomeString.IsNull || _IsEmpty)
{
return;
}
if (SomeString.Value.Trim() == String.Empty)
{
_IsEmpty = true;
_Matches.Clear();
_TempFirstValue = String.Empty;
return;
}
if (_IsFirstComparison)
{
if (_TempFirstValue == String.Empty)
{
_TempFirstValue = SomeString.Value;
return;
}
if (ExtractSubstrings(SomeString.Value, _TempFirstValue) == 0)
{
_IsEmpty = true;
}
_TempFirstValue = String.Empty;
_IsFirstComparison = false;
return;
}
RemoveMissingMatches(SomeString.Value);
if (_Matches.Count == 0)
{
_IsEmpty = true;
}
return;
}
private void RemoveMissingMatches(string SearchIn)
{
for (int _Index = 0; _Index < _Matches.Count; _Index++)
{
if (SearchIn.Length >= _Matches[_Index].Length &&
SearchIn.IndexOf(_Matches[_Index], StringComparison.InvariantCultureIgnoreCase) >= 0)
{
continue;
}
_Matches.RemoveAt(_Index);
_Index--; // prevent skipping due to following entries shifting down 1
}
return;
}
private int ExtractSubstrings(string SearchIn, string SearchFor)
{
string _TempString;
int _TempMaxLength = 0;
bool _AlreadyInCollection;
if (SearchIn.Length < SearchFor.Length)
{
// switch
_TempString = SearchFor;
SearchFor = SearchIn;
SearchIn = _TempString;
}
for (int _SearchForLength = SearchFor.Length; _SearchForLength > 0 ; _SearchForLength--)
{
for (int _Index = 0; (_Index + _SearchForLength) <= SearchFor.Length; _Index++)
{
_TempString = SearchFor.Substring(_Index, _SearchForLength);
if (SearchIn.IndexOf(_TempString, StringComparison.InvariantCultureIgnoreCase) >= 0)
{
if (_TempMaxLength == 0)
{
_TempMaxLength = _SearchForLength;
}
_AlreadyInCollection = false;
for (int _MatchIndex = 0; _MatchIndex < _Matches.Count; _MatchIndex++)
{
if(_Matches[_MatchIndex].Equals(_TempString, StringComparison.InvariantCultureIgnoreCase))
{
_AlreadyInCollection = true;
break;
}
}
if (!_AlreadyInCollection) // no duplicates
{
_Matches.Add(_TempString);
}
}
}
}
return _TempMaxLength;
}
private List<int> GetMaxLengthItems()
{
int _MaxMatchLength = 0;
List<int> _MaxLengthMatches = new List<int>();
for (int _Index = 0; _Index < _Matches.Count; _Index++)
{
if (_Matches[_Index].Length > _MaxMatchLength)
{
_MaxLengthMatches.Clear();
_MaxLengthMatches.Add(_Index);
_MaxMatchLength = _Matches[_Index].Length;
continue;
}
if (_Matches[_Index].Length == _MaxMatchLength)
{
_MaxLengthMatches.Add(_Index);
}
}
return _MaxLengthMatches;
}
public void Merge (LongestCommonSubstring Incoming)
{
_HasMerged = true;
if (_IsEmpty || Incoming._IsEmpty)
{
_IsEmpty = true;
_Matches.Clear();
_TempFirstValue = String.Empty;
return;
}
if (_IsFirstComparison)
{
if (_TempFirstValue == String.Empty)
{
if (Incoming._IsFirstComparison)
{
_TempFirstValue = Incoming._TempFirstValue;
}
else
{
_IsFirstComparison = false;
_Matches = Incoming._Matches;
}
return;
}
else
{
if (Incoming._IsFirstComparison)
{
if (Incoming._TempFirstValue != String.Empty)
{
Accumulate(Incoming._TempFirstValue, _ReturnAllSubstrings.Value);
}
}
else
{
string _Temp = _TempFirstValue;
_TempFirstValue = String.Empty;
_IsFirstComparison = false;
_Matches = Incoming._Matches;
Accumulate(_Temp, _ReturnAllSubstrings.Value);
}
return;
} // if (_TempFirstValue == String.Empty) else
} // if (_IsFirstComparison)
else
{
if (Incoming._IsFirstComparison)
{
if (Incoming._TempFirstValue != String.Empty)
{
Accumulate(Incoming._TempFirstValue, _ReturnAllSubstrings.Value);
}
}
else
{
bool _MatchExists;
for (int _Index = 0; _Index < _Matches.Count; _Index++)
{
_MatchExists = false;
for (int _IncomingIndex = 0; _IncomingIndex < Incoming._Matches.Count; _IncomingIndex++)
{
if (String.Equals(_Matches[_Index], Incoming._Matches[_IncomingIndex],
StringComparison.InvariantCultureIgnoreCase))
{
_MatchExists = true;
break;
}
}
if (!_MatchExists)
{
_Matches.RemoveAt(_Index);
_Index--; // prevent skipping due to following entries shifting down 1
}
}
if (_Matches.Count == 0)
{
_IsEmpty = true;
}
} // if (Incoming._IsFirstComparison) else
} // if (_IsFirstComparison) else
return;
}
public SqlXml Terminate()
{
if (_IsEmpty)
{
return new SqlXml(XmlReader.Create(new StringReader("<Items Merged=\"" + _HasMerged.ToString() + "\"></Items>")));
}
if (!_IsEmpty && _IsFirstComparison)
{
return SqlXml.Null;
}
List<int> _MatchIndexesToReturn = GetMaxLengthItems();
XmlDocument _AllItems = new XmlDocument();
XmlElement _Items = _AllItems.CreateElement("Items");
_Items.SetAttribute("Merged", _HasMerged.ToString());
if (!_ReturnAllSubstrings.Value)
{
for (int _Index = 0; _Index < _MatchIndexesToReturn.Count; _Index++)
{
XmlElement _TempElement = _AllItems.CreateElement("Item");
_TempElement.InnerText = _Matches[_MatchIndexesToReturn[_Index]];
_Items.AppendChild(_TempElement);
}
}
else
{
for (int _Index = 0; _Index < _Matches.Count; _Index++)
{
XmlElement _TempElement = _AllItems.CreateElement("Item");
_TempElement.InnerText = _Matches[_Index];
_TempElement.SetAttribute("IsLongest", _MatchIndexesToReturn.Contains(_Index).ToString());
_Items.AppendChild(_TempElement);
}
}
_AllItems.AppendChild(_Items);
return new SqlXml(XmlReader.Create(new StringReader(_AllItems.OuterXml)));
}
public void Read(BinaryReader Reader)
{
_ReturnAllSubstrings = Reader.ReadBoolean();
_HasMerged = Reader.ReadBoolean();
_IsEmpty = Reader.ReadBoolean();
// no sense in doing extra work if there can't be any matches
if (!_IsEmpty)
{
_TempFirstValue = Reader.ReadString();
_IsFirstComparison = Reader.ReadBoolean();
int _TempMatchCount = Reader.ReadInt32();
_Matches = new List<string>();
for (int _Index = 0; _Index < _TempMatchCount; _Index++)
{
_Matches.Add(Reader.ReadString());
}
}
return;
}
public void Write(BinaryWriter Writer)
{
Writer.Write(_ReturnAllSubstrings.Value); // bool
Writer.Write(_HasMerged); // bool
Writer.Write(_IsEmpty); // bool
// no sense in doing extra work if there can't be any matches
if (!_IsEmpty)
{
Writer.Write(_TempFirstValue); // string
Writer.Write(_IsFirstComparison); // bool
Writer.Write(_Matches.Count); // int
for (int _Index = 0; _Index < _Matches.Count; _Index++)
{
Writer.Write(_Matches[_Index]);
}
}
return;
}
}
Comments