思路

SAM的概念题

暴力模拟就好了

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

set<int> St[2511];

const int base = 131;

int setcnt=0,minlens[2511],minlent[2511],maxlens[2511],maxlent[2511],n,lens,lent;

char s[2511],t[2511];

unsigned long long hashs[120],powh[120];

void init(void){

    for(int i=1;i<=2510;i++){

        minlent[i]=0x3f3f3f3f;

        maxlens[i]=1;

    }

    powh[0]=1;

    for(int i=1;i<=100;i++)

        powh[i]=powh[i-1]*base;

}

unsigned long long hashf(int l,int r){

    return hashs[r]-hashs[l-1]*powh[r-l+1];

}

int main(){

    init();

    scanf("%s",s+1);

    lens=strlen(s+1);

    for(int i=1;i<=lens;i++){

        hashs[i]=hashs[i-1]*base+s[i];

    }

    for(int l=1;l<=lens;l++)

        for(int r=l;r<=lens;r++){

            set<int> S;

            while(S.size())

                S.erase(S.begin());

            for(int i=1;i<=lens-(r-l+1)+1;i++)

                if(hashf(i,i+(r-l+1)-1)==hashf(l,r))

                    S.insert(i+(r-l+1)-1);

            bool f=false;

            // for(int k=l;k<=r;k++)

            //     putchar(s[k]);

            // putchar('\n');

            // for(set<int>::iterator it=S.begin();it!=S.end();it++)

            //     printf("%d ",(*it));

            // printf("\n");

            for(int i=1;i<=setcnt;i++){

                if(S==St[i]){

                    // printf("into %d\n",i);

                    f=true;

                    if(minlent[i]-minlens[i]+1>r-l+1){

                        minlent[i]=r;

                        minlens[i]=l;

                    }

                    if(maxlent[i]-maxlens[i]+1<r-l+1){

                        maxlent[i]=r;

                        maxlens[i]=l;

                    }

                    break;

                }

            }

            if(!f){

                // printf("New\n");

                ++setcnt;

                St[setcnt]=S;

                minlens[setcnt]=maxlens[setcnt]=l;

                minlent[setcnt]=maxlent[setcnt]=r;

            }

        }

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%s",t+1);

        lent=strlen(t+1);

        unsigned long long hashval=0;

        set<int> S;

        while(S.size())

            S.erase(S.begin());

        for(int j=1;j<=lent;j++)

            hashval=hashval*base+t[j];

        // printf("hasf=%lld %lld\n",hashf(2,5),hashval);

        for(int j=1;j<=lens-lent+1;j++)

            if(hashf(j,j+lent-1)==hashval)

                S.insert(j+lent-1);

        // for(set<int>::iterator it=S.begin();it!=S.end();it++)

        //     printf("%d ",(*it));

        // printf("\n");

        for(int j=1;j<=setcnt;j++){

            if(S==St[j]){

                for(int k=minlens[j];k<=minlent[j];k++)

                    putchar(s[k]);

                putchar(' ');

                for(int k=maxlens[j];k<=maxlent[j];k++)

                    putchar(s[k]);

                putchar(' ');

                for(set<int>::iterator it = S.begin();it!=S.end();it++)

                    printf("%d ",(*it));

                printf("\n");

                break;

            }

        }

    }

    return 0;

}