Algorithms/String_Matching_Using_Suffix_Array.cpp at master · asimali246/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <vector>
#include <fstream>
#include <map>
#include <bitset>
#include <cstring>
using namespace std;
#define ll long long int
#define inf 2147483647
#define pi acos(-1)
#define EPS 1e-9
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, ll> llp;
#define Max 1000010
int n, m;
char T[Max];
int RA[Max], tempRA[Max];
int SA[Max], tempSA[Max];
int c[Max];
char P[Max];
void countingSort(int k)
{
    int i, sum, maxi=max(300, n);
    memset(c, 0, sizeof c);
    for(i=0;i<n;++i)
        c[i+k<n?RA[i+k]:0]++;
    for(i=sum=0;i<maxi;++i)
    {
        int t=c[i];
        c[i]=sum;
        sum+=t;
    }
    for(i=0;i<n;++i)
        tempSA[c[SA[i]+k<n?RA[SA[i]+k]:0]++]=SA[i];
    for(i=0;i<n;++i)
        SA[i]=tempSA[i];
}
void constructSA()
{
    int i, k, r;
    for(i=0;i<n;++i)
        RA[i]=T[i]-'.';
    for(i=0;i<n;++i)
        SA[i]=i;
    for(k=1;k<n;k<<=1)
    {
        countingSort(k);
        countingSort(0);
        tempRA[SA[0]]=r=0;
        for(i=1;i<n;++i)
            tempRA[SA[i]]=(RA[SA[i]]==RA[SA[i-1]] && RA[SA[i]+k]==RA[SA[i-1]+k])?r:++r;
        for(i=0;i<n;++i)
            RA[i]=tempRA[i];
    }
}
ii stringMatching()
{
    int lo=0, hi=n-1, mid=lo;
    while(lo<hi)
    {
        mid=(lo+hi)>>1;
        int res=strncmp(T+SA[mid], P, m);
        if(res>=0)hi=mid;
        else
            lo=mid+1;
    }
    if(strncmp(T+SA[lo], P, m)!=0)
        return ii(-1, -1);
    ii ans;
    ans.first=lo;
    lo=0;
    hi=n-1;
    mid=lo;
    while(lo<hi)
    {
        mid=(lo+hi)>>1;
        int res=strncmp(T+SA[mid], P, m);
        if(res>0)hi=mid;
        else
            lo=mid+1;
    }
    if(strncmp(T+SA[hi], P, m)!=0)hi--;
    ans.second=hi;
    return ans;
}
int main()
{
    n=(int)strlen(gets(T));
    constructSA();
    for(int i=0;i<n;++i)
        printf("%2d\t%s\n", SA[i], T+SA[i]);
    while(m=(int)strlen(gets(P)), m)
    {
        ii pos=stringMatching();
        if(pos.first!=-1 && pos.second!=-1)
        {
            printf("%s is found SA [%d..%d] of %s\n", P, pos.first, pos.second, T);
            printf("They are:\n");
            for(int i=pos.first;i<=pos.second;++i)
                printf("  %s\n", T+SA[i]);
        }
        else
            printf("%s is not found in %s\n", P, T);
    }
    return 0;
}