SP8093 JZPGYZ - Sevenk Love Oimaster

广义后缀自动机……

其实也不是很难理解，就是每次SAM插入一个串之后，插入新的串的时候，要把last重新调到1的位置，共用一些节点。

这个题我们首先要预处理出来每个状态被多少个串共用。挺暴力的就是每次把节点染色，如果节点没被染色就给他染一下，然后记录当前节点又被共用了一次。

最后跑的时候和匹配是一样的，每次输出末尾节点共用次数即可。

#include<bits/stdc++.h>

#define rep(i,a,n) for(register int i = a;i <= n;i++)

#define per(i,n,a) for(register int i = n;i >= a;i--)

#define enter putchar('\n')

#define pr pair<int,int>

#define mp make_pair

#define fi first

#define sc second

using namespace std;

typedef long long ll;

const int M = 100005;

const int N = 10000005;

const int INF = 2147483647;

int read()

{

   int ans = 0,op = 1;

   char ch = getchar();

   while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}

   while(ch >='0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();

   return ans * op;

}

string s[M],t;

int n,m,k,times[M<<1],col[M<<1];

struct Suffix

{

   int last,cnt,ch[M<<1][26],fa[M<<1],l[M<<1];

   void extend(int c)

   {

      int p = last,np = ++cnt;

      last = cnt,l[np] = l[p] + 1;

      while(p && !ch[p][c]) ch[p][c] = np,p = fa[p];

      if(!p) {fa[np] = 1;return;}

      int q = ch[p][c];

      if(l[q] == l[p] + 1) fa[np] = q;

      else

      {

     int nq = ++cnt;

     l[nq] = l[p] + 1,memcpy(ch[nq],ch[q],sizeof(ch[q]));

     fa[nq] = fa[q],fa[q] = fa[np] = nq;

     while(ch[p][c] == q) ch[p][c] = nq,p = fa[p];

      }

   }

   void cal(string b,int q)

   {

      int cur = 1,h = b.length();

      rep(j,0,h-1)

      {

     cur = ch[cur][b[j] - 'a'];

     int t = cur;

     while(t && col[t] != q) times[t]++,col[t] = q,t = fa[t];

      }

   }

   void match(string b)

   {

      int cur = 1;

      rep(i,0,k-1) cur = ch[cur][b[i]-'a'];

      printf("%d\n",times[cur]);

   }

}SAM;

int main()

{

   n = read(),m = read();

   SAM.cnt = 1;

   rep(i,1,n)

   {

      cin >> s[i],k = s[i].length();

      SAM.last = 1;

      rep(j,0,k-1) SAM.extend(s[i][j] - 'a');

   }

   rep(i,1,n) SAM.cal(s[i],i);

   while(m--) cin >> t,k = t.length(),SAM.match(t);

   return 0;

}

巴特西

SP8093 JZPGYZ - Sevenk Love Oimaster

最新文章

热门文章