LiveArchive #2164

#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;
#define nullptr 0

struct link{
  int key;
  link* to;
  link(int key=0,link* pre=nullptr): key(key), to(pre){}
};
link link_pre[2400]; int link_prec;

struct aho{
  aho* to[26];
  aho* fail;
  link* match;
  static aho prep[2400];
  static int prec;

  aho(){for (int i=26; i--;) to[i]=nullptr; match=nullptr;}

  void insert(char const* str,int id){
    if (not *str) match=new(link_pre+link_prec++) link(id,match);
    else (to[*str-'a']=(to[*str-'a']?to[*str-'a']:new(prep+prec++) aho))->insert(str+1,id);
  }

  void build(){
    fail=this;
    queue<pair<aho*,unsigned char> > bfs;
    for (bfs.push(make_pair(this,0)); not bfs.empty(); bfs.pop()){
      aho* on=bfs.front().first; unsigned char c=bfs.front().second;
      while (on->fail!=this and not on->fail->to[c]) on->fail=on->fail->fail;
      if (on!=this and on->fail->to[c] and on->fail->to[c]!=on) on->fail=on->fail->to[c];
      link* m=on->match; while (m and m->to) m=m->to;
      (m?m->to:on->match)=on->fail->match;
      for (int i=26; i--;) if (on->to[i]) bfs.push(make_pair(on->to[i],i)), on->to[i]->fail=on->fail;
    }
  }
};
aho aho::prep[2400];
int aho::prec;

char buf[5002];
int sum[5002];
int got[5002][24];
int goc[6000];
int len[24];

bool did[5002][4096];
bool dfs(int i,short need,short mask){
  if (not need) return true;
  if (did[i][mask]) return false; else did[i][mask]=true;
  for (int j=goc[i]; j--;)
    if (not (mask&(1<<got[i][j]))){
      if (dfs(i-len[got[i][j]],need-1,mask|(1<<got[i][j]))) return true;
    }
  return false;
}

int const cash[26]={
   2, 3, 5, 7,11,
  13,17,19,23,29,
  31,37,41,43,47,
  53,59,61,67,71,
  73,79,83,89,97,
  101
};

int main(){
  #ifdef twentyone
  freopen("searchcat.in","r",stdin);
  #endif

  for (;;){
    sum[0]=0;
    link_prec=0;
    aho::prec=0;
    aho corasick;
    int tot=0,want=0;
    memset(did,0,sizeof did);
    int n,m; scanf("%d %d",&n,&m); if (n+m==0) break;
    for (int i=0;     i<n; i++){scanf(" %s",buf); corasick.insert(buf,i); tot+=(len[i]=strlen(buf)); for (int j=0; buf[j]; j++) want+=cash[buf[j]-'a'];}
    for (int i=0,j=0; i<m; i++) scanf(" %s",buf+j), j+=strlen(buf+j);
    corasick.build();
    aho* on=&corasick;
    int res=0;
    for (int i=0; buf[i]; i++){
      goc[i]=0, sum[i+1]=sum[i]+cash[buf[i]-'a'];
      while (on!=&corasick and not on->to[buf[i]-'a']) on=on->fail; if (on->to[buf[i]-'a']) on=on->to[buf[i]-'a'];
      for (link* with=on->match; with; with=with->to) got[i][goc[i]++]=with->key;
      if (i+1>=tot and sum[i+1]-sum[i-tot+1]==want) res+=dfs(i,n,0);
    }
    printf("%d\n",res);
  }
}