Massive Algorithms: String Search

Showing posts with label String Search. Show all posts

String SubString Search

Brute Force:
http://algs4.cs.princeton.edu/53substring/Brute.java.html

    // return offset of first match or N if no match
    public static int search1(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; i++) {
            int j;
            for (j = 0; j < M; j++) {
                if (txt.charAt(i+j) != pat.charAt(j))
                    break;
            }
            if (j == M) return i;            // found at offset i
        }
        return N;                            // not found
    }

    // return offset of first match or N if no match
    public static int search2(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();
        int i, j;
        for (i = 0, j = 0; i < N && j < M; i++) {
            if (txt.charAt(i) == pat.charAt(j)) j++;
            else {
                i -= j;
                j = 0;
            }
        }
        if (j == M) return i - M;    // found
        else        return N;        // not found
    }

http://www.stoimen.com/blog/2012/03/27/computer-algorithms-brute-force-string-matching/

function sub_string($pattern, $subject) 
{
 $n = strlen($subject);
 $m = strlen($pattern);
 
 for ($i = 0; i < $n-$m; $i++) {
  $j = 0;
  while ($j < $m && $subject[$i+$j] == $pattern[$j]) {
   $j++;
  }
  if ($j == $m) return $i;
 }
 return -1;
}

Data Structures and Algorithms in Java, 6th Edition
BOYER-MOORE
Looking-Glass Heuristic: When testing a possible placement of the pattern against the text, perform the comparisons against the pattern from right-to-left.

Character-Jump Heuristic: During the testing of a possible placement of the pattern within the text, a mismatch of character text[i]=c with the corresponding character pattern[k] is handled as follows. If c is not contained anywhere in the pattern, then shift the pattern completely past text[i] = c. Otherwise, shift the pattern until an occurrence of character c gets aligned with text[i].

when a mismatch is found near the right end of the pattern, we may end up realigning the pattern beyond the mismatch, without ever examining several characters of the text preceding the mismatch.

Notice that when the characters e and i mismatch at the right end of the original placement of the pattern, we slide the pattern beyond the mismatched character, without ever examining the first four characters of the text.

The original comparison results in a mismatch with character e of the text. Because that character is nowhere in the pattern, the entire pattern is shifted beyond its location. The second comparison is also a mismatch, but the mismatched character s occurs elsewhere in the pattern. The pattern is then shifted so that its last occurrence of s is aligned with the corresponding s in the text.

If the mismatched character occurs elsewhere in the pattern, we must consider two possible subcases depending on whether its last occurrence is before or after the character of the pattern that was mismatched.

we slide the pattern only one unit. It would be more productive to slide it rightward until finding another occurrence of mismatched character text[i] in the pattern, but we do not wish to take time to search for another occurrence. The efficiency of the Boyer-Moore algorithm relies on quickly determining where a mismatched character occurs elsewhere in the pattern. In particular, we define a function last(c) as
If c is in the pattern, last(c) is the index of the last (rightmost) occurrence of c in the pattern. Otherwise, we conventionally define last(c) = −1.

Additional rules for the character-jump heuristic of the Boyer-Moore algorithm. We let i represent the index of the mismatched character in the text, k represent the corresponding index in the pattern, and j represent the index of the last occurrence of text[i] within the pattern. We distinguish two cases: (a) j < k, in which case we shift the pattern by k − j units, and thus, index i advances by m − (j + 1) units; (b) j > k, in which case we shift the pattern by one unit, and index i advances by m − k units.

We prefer to use a hash table to represent the last function, with only those characters from the pattern occurring in the map. The space usage for this approach is proportional to the number of distinct alphabet symbols that occur in the pattern, and thus O(max(m, |Σ|)).

The correctness of the Boyer-Moore pattern-matching algorithm follows from the fact that each time the method makes a shift, it is guaranteed not to “skip” over any possible matches.

If using a traditional lookup table, the worst-case running time of the Boyer-Moore algorithm is O(nm + |Σ|). The computation of the last function takes O(m+|Σ|) time, although the dependence on |Σ| is removed if using a hash table. The actual search for the pattern takes O(nm) time in the worst case

The original algorithm achieves worst-case running time O(n + m + |Σ|) by using an alternative shift heuristic for a partially matched text string, whenever it shifts the pattern more than the character-jump heuristic. This alternative shift heuristic is based on applying the main idea from the Knuth-Morris-Pratt pattern-matching algorithm.

Jobdu-1535-重叠的最长子串[扩展KMP] | Acm之家

九度-1535-重叠的最长子串[扩展KMP] | Acm之家
给定两个字符串，求它们前后重叠的最长子串的长度，比如"abcde"和"cdefg"是"cde"，长度为3。

对于每个测试案例只有一行，包含两个字符串。字符串长度不超过1000000，仅包含字符’a'-’z'。

X. KMP
http://arc9.riaos.com/?p=5077
http://blog.csdn.net/a1dark/article/details/16994887
咋一看貌似KMP扩展、其实只需要普通的KMP就可以解决、不过需要重新构造一个新字符串C=B+A、于是求出字符串C的next值、最后的值便是answer、
abcde cdefg
==> s3: cdefgabcde, use MKP to compute next or failure function.

int getnext(){
    int j=0,k=-1;
    next[0]=-1;
    int len=strlen(str3);
    while(j<len){
        if(k==-1||str3[j]==str3[k]){
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
    int ans=0;
    ans=min(len1,len2);
    ans=min(ans,k);
    return ans;
}

        len1=strlen(str1);
        len2=strlen(str2);
        memset(str3,'',sizeof(str3));
        for(int i=0;i<len2;i++){
            str3[i]=str2[i];
        }
        for(int i=len2,j=0;i<len1+len2,j<len1;i++,j++){
            str3[i]=str1[j];
        }

X. KMP Extended http://blog.csdn.net/xiaozhuaixifu/article/details/12348123

扩展KMP，用extend[i]保存主串 S[i.....n-1]与模式串 T的最长公共前缀的长度，其中n是S的长度。

然后扫描一遍 extend[] 如 extend[i] == n-i 那么这个后缀的长度就是我们要求的值。

关于扩展KMP，可以去看论文：《求最长回文子串与最长重复子串》何林的集训队论文

void getnext(char *T)
{
int k = 0;
int Tlen = strlen(T);
next[0] = Tlen;
while(k < Tlen-1 && T[k] == T[k+1])
k++;
next[1] = k;
k = 1;
for(int i = 2; i < Tlen; i++)
{
int p = k+next[k]-1, L = next[i-k]; // p :=已经匹配到的最远的位置
// L :=
if((i-1)+L >= p)
{
int j=(p-i+1)>0? p-i+1:0;
while(i+j < Tlen && T[k+j]==T[j])
j++;
next[i] = j;
k = i;
}
else next[k]=L;
}
}
void getextend(char *S,char *T)
{
int a = 0;
getnext(T);
int Slen = strlen(S);
int Tlen = strlen(T);
int len = Slen<Tlen ? Slen:Tlen;
while(a < len && S[a] == T[a]) a++;
extend[0] = a;
a = 0;
for(int i = 1; i < Slen; i++)
{
int p = a + extend[a]-1, L = next[i-a];
if(i+L-1 >= p)
{
int j = (p-i+1)>0? p-i+1:0;
while(i+j < Slen && j<Tlen && S[i+j] == T[j])
j++;
extend[i] = j;
a = i;
}
else extend[i] = L;
}
}

getextend(S,T);
int n = strlen(S);
int res = 0;
for(int i = 0; i < n; i++)
{
if(extend[i] == n-i)
{
res = extend[i];
break;
}
}
cout<<res<<endl;

X. Brute Force

int judge(char *s,char *t,int low,int high){

05    int index_t = 0;

06    int len_t = strlen(t);

07    while(low <= high)

08    {

09        if(s[low] != t[index_t]) return 0;

10        ++low;

11        ++index_t;

12    }

13    return 1;

14}

15

16int main()

17{

18    char s[M],t[M];

19    int len_s,len_t,i,flag;

20    while(~scanf("%s%s",s,t))

21    {

22        flag = 0;

23        len_s = strlen(s);

24        len_t = strlen(t);

25        i = len_s > len_t ? len_s-len_t : 0;//减少判断，s串短，从0开始判断，s串长，从len_s-len_t位置开始判断。

26        for(; i < len_s ;++i)

27        {

28            if(s[i] == t[0] && judge(s,t,i,len_s -1))

29            {

30                printf("%d\n",len_s - i);

31                flag = 1;

32                break;

33            }

34        }

35        if(!flag) printf("0\n");

36    }

37    return 0;

38}

X. Rolling Hash
http://blog.csdn.net/xiaozhuaixifu/article/details/12348123

下面介绍一种滚动哈希算法：假设要求S的后缀和T的前缀相等的最大长度，也可以利用滚动哈希在O（n+m）的时间内求解：
假设字符串C = c1c2....cm 定义哈希函数：
H(C) = (c1*b^(m-1)+c2*b^(m-2)+.....+cm*b^(0)) mod h ，
其中 b和h是两个互素的数，这样，我们就可以将字符串 S=s1s2...sn 从位置 k+1 开始长度为m的子串 S[k+1....k+m]的哈希值
根据子串 S[k....k+m-1]的哈希值在常数
时间内求出来：
H(S[k+1....k+m]) = H(S[k..k+m-1]*b - sk*b^m +s(k+m)) mod h ，
只要不断这样右移，就可以在O（n）的时间内求得所有位置的哈希值

int overlap(string &a,string &b)
{
int alen = a.size(), blen = b.size();
int res = 0;
ull ahash = 0, bhash = 0, t = 1;
for(int i = 1; i <= min(alen,blen); i++)
{
ahash = ahash + (a[alen-i]-'a')*t; //a的长度为i的后缀哈希值
bhash = bhash*B + b[i-1]-'a'; //b的长度为i的前缀哈希值
if(ahash == bhash) res = i;
t *= B;
}
return res;
}

http://blog.csdn.net/taoqick/article/details/38470057

int maxLen(const char* S, const char* T) {
int Slen = strlen(S), Tlen = strlen(T), i, j, minLen = min(Slen, Tlen), res = 0;
typedef unsigned long long ull;
ull Shash = 0, Thash = 0, t = 1, radix = 100000007;
for (int i = 1; i <= minLen; ++i) {
Shash = Shash + (S[Slen-i] - 'a') * t;
Thash = Thash * radix + (T[i-1] - 'a');
t *= radix;
if (Shash == Thash)
res = i;
}
return res;
}

Read full article from 九度-1535-重叠的最长子串[扩展KMP] | Acm之家

String SubString Search

Jobdu-1535-重叠的最长子串[扩展KMP] | Acm之家

Labels

Popular Posts