HDU 5384 Danganronpa

Problem Description

Danganronpa is a video game franchise created and developed by Spike Chunsoft, the series' name is compounded from the Japanese words for "bullet" (dangan) and "refutation" (ronpa).

Now, Stilwell is playing this game. There are 

n verbal evidences, and Stilwell has 

m "bullets". Stilwell will use these bullets to shoot every verbal evidence.

Verbal evidences will be described as some strings 

Ai, and bullets are some strings 

Bj. The damage to verbal evidence 

Ai from the bullet 

Bj is 

f(Ai,Bj).

f(A,B)=∑i=1|A|−|B|+1[ A[i...i+|B|−1]=B ]

In other words, 

f(A,B) is equal to the times that string 

B appears as a substring in string 

A.

For example: 

f(ababa,ab)=2, 

f(ccccc,cc)=4

Stilwell wants to calculate the total damage of each verbal evidence 

Ai after shooting all 

m bullets 

Bj, in other words is 

∑mj=1f(Ai,Bj).

Input

T, the number of test cases.

For each test case, the first line contains two integers 

n, 

m.

Next 

n lines, each line contains a string 

Ai, describing a verbal evidence.

Next 

m lines, each line contains a string 

Bj, describing a bullet.

T≤10

For each test case, 

n,m≤105, 

1≤|Ai|,|Bj|≤104, 

∑|Ai|≤105, 

∑|Bj|≤105

For all test case, 

∑|Ai|≤6∗105, 

∑|Bj|≤6∗105, 

Ai and 

Bj

Output

n lines, each line contains a integer describing the total damage of 

Ai from all 

m bullets, 

∑mj=1f(Ai,Bj).

Sample Input

1
5 6
orz
sto
kirigiri
danganronpa
ooooo
o
kyouko
dangan
ronpa
ooooo
ooooo      

Sample Output

1
1
0
3
7      

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int size = 26;//字典樹節點大小
const int base = 'a';//字典樹
const int maxn = 100005;//字典樹大小（便于各種操作）

class tire
{
public:
    tire *next[size], *fail;
    ll cnt, id;
    //各種節點設定
    tire(){ cnt = 0; fail = NULL; memset(next, 0, sizeof(next)); };
};//字典樹節點設定

class Ac_machine
{
private:
    tire *root;//根節點建立
    tire *node[maxn];//與id相對立，便于各種操作
    int tot;//字典樹大小
    char s[maxn];//讀入字元串
public:
    char S[maxn];//母串
    Ac_machine(){}
    void clear(){ node[0] = root = new tire; tot = 0; }//初始化
    void insert(int);//插入多個字元串
    int insert();//插入字元串,傳回字元串大小
    void getfail();    //擷取失配指針
    int getmother();//獲得比對的母串，傳回母串大小
    int work_out();//求解函數，依照題目不同而不同,傳回答案
}ac;//ac自動機設定

int Ac_machine::getmother(){ scanf("%s", S); return strlen(S); }

void Ac_machine::insert(int n){ while (n--) insert(); }

int Ac_machine::insert()
{
    scanf("%s", s);
    tire *now = root;
    for (int i = 0, k; s[i]; i++)
    {
        k = s[i] - base;
        if (!now->next[k])
        {
            node[++tot] = now->next[k] = new tire;
            now->next[k]->id = tot;
        }
        now = now->next[k];
    }
    now->cnt++;
    //可以插入一些字典樹的設定
    return strlen(s);
}

void Ac_machine::getfail()
{
    queue<tire*> p;
    root->fail = root;
    for (int i = 0; i < size; i++)
    if (root->next[i])
    {
        root->next[i]->fail = root;
        p.push(root->next[i]);
    }
    else root->next[i] = root;

    tire *now;
    while (!p.empty())
    {
        now = p.front();    p.pop();
        now->cnt += now->fail->cnt;
        //可以插入統計子串個數等操作
        for (int i = 0; i < size; i++)
        if (now->next[i])
        {
            now->next[i]->fail = now->fail->next[i];
            p.push(now->next[i]);
        }
        else now->next[i] = now->fail->next[i];
    }
}

int Ac_machine::work_out()
{
    ll ans = 0;
    tire *now = root;
    //for (int i = 0; i < maxn; i++) printf("%d\n", node[i]->cnt);
    for (int i = 0, k; S[i]; i++)
    {
        k = S[i] - base;
        now = now->next[k];
        ans += now->cnt;
    }
    return ans;//傳回子串出現次數
}

vector<char> p[maxn];
char s[maxn];

int main()
{
    int T,n,m;
    scanf("%d",&T);
    while (T--)
    {
        ac.clear();
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
        {
            p[i].clear();
            scanf("%s",s);
            for (int j=0;s[j];j++) p[i].push_back(s[j]);
        }
        ac.insert(m);
        ac.getfail();
        for (int i=1;i<=n;i++)
        {
            for (int j=0;j<p[i].size();j++)
            {
                ac.S[j]=p[i][j];
            }
            ac.S[p[i].size()]=0;
            printf("%lld\n",ac.work_out());
        }
    }
}