#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef std::pair P; typedef std::pair PP; const ll MOD=998244353; map stringid; vector ans; struct Aho_Corasick{ typedef std::unordered_map MP; std::vector trie; std::vector cnt;//cnt,treeの大きさは同じ const int root=0; Aho_Corasick(){ trie.push_back(MP()); cnt.push_back(0); } std::unordered_map> output; void add(const std::vector& terms){ for(const std::string& term:terms){ add(term); } } //計算量は挿入する文字列の長さの和 int add(const std::string& string){ int now=root;//根 for(char c:string){ if(trie[now].count(c)){ now=trie[now][c]; }else{ int pre=now; now=trie.size(); cnt.push_back(0); trie.push_back(MP()); trie[pre][c]=now; } } cnt[now]++;//終端文字列 output[now].push_back(string);//終端ノードに対してsを入れる return now; } void match(const std::string& string){ //std::cout<<"target: string="< failure; std::vector dist; //ノードnowから文字列cをうけていく場所 std::optional go(int now,char c){ if(trie[now].count(c)){ return trie[now][c]; }else if(now==root) return root; else return {}; } void bfs(){ failure=std::vector(trie.size(),0); dist=std::vector(trie.size(),-1); std::queue que; dist[root]=0; que.push(root); while(!que.empty()){ int now=que.front(); que.pop(); for(auto [c,to]:trie[now]){ //nowのキーc,toを取り出す //trie[now][c]=toとなる if(now!=root){ int f=failure[now];//nowで失敗した場合に行きつく場所 while(!go(f,c)){ f=failure[f]; } //go(f,c).firstがtrueつまり状態fの次に文字cで行ける場所がある もしくはfがroot failure[to]=*go(f,c); for(const auto& string:output[failure[to]]){ //ノードfailure[to]で終わる文字列たちをtoにもいれる output[to].push_back(string); } } que.push(to); dist[to]=dist[now]+1; } } } }; int main(){ string S; cin>>S; int M; cin>>M; ans=vector(M,0); Aho_Corasick aho; vector C(M); for(int i=0;i>C[i]; aho.add(C[i]); } aho.bfs(); aho.match(S); ll cntans=0; for(int i=0;i