Description
Zplinti1 is given a big and long string
, together with a list of strings that are viruses. He wants to find the number of substrings of
, so that it does not contain any viruses. Same substrings with different starting positions are regarded as different!
Zplinti1 finds this problem difficult enough, he thinks
Only God Can Solve This Problem
, but you don’t think so, right?
Input
The first line of input contains a number
, indicating the number of cases. (
)
For each case, the first line is a string
, with length no more than
. The second line is a number
, which is the number of virus strings. Then
All the strings contains lowercase letters from
a
to
z
only. The total length of all virus strings in one case will be no more than
.
Output
For each case, output
Case #i:
first. (
is the number of the test case, from
to
). Then output the number of substrings of
Sample Input
3
aabc
aabbaa
1
a
abcdefg
2
bcd
ef
Sample Output
Case #1: 10
Case #2: 3
Case #3: 14
Hint
A substring of a string
is a continuous string taken from
. For example if we take out the letters from the
to the
of the string, then the substring will be (
).
The original string is a substring of itself.
When we say string
contains
string
, it means that
is a substring of
.
Source
The 11th UESTC Programming Contest Final
#include<stdio.h>
#include<string.h>
#include<queue>
#include<malloc.h>
using namespace std;
const int maxn = 1000005;
int T, n, t = 0;
long long ans;
class tire
{
public:
tire *down[26], *next;
int end;
tire(){ next = NULL; end = 0; memset(down, 0, sizeof(down)); }
void assign(){ next = NULL; end = 0; memset(down, 0, sizeof(down)); }
};
class ac_automaton
{
private:
tire *root;
char s[maxn];
char S[maxn];
public:
ac_automaton(){ root = new tire; }
void insert()
{
scanf("%s",s);
tire* j = root;
for (int i = 0, k; s[i]; i++)
{
k = s[i] - 'a';
if (!j->down[k]) j->down[k] = new tire;
j = j->down[k];
}
j->end = strlen(s);
}
void getnext()
{
queue<tire*> p;
tire *q, *k, *j;
root->next = root;
for (int i = 0; i < 26; i++)
if (root->down[i])
{
q = root->down[i];
q->next = root;
p.push(q);
}
else root->down[i] = root;
while (!p.empty())
{
q = p.front(); p.pop();
k = q->next;
for (int i = 0; i < 26; i++)
if (q->down[i])
{
j = q->down[i];
if (k->down[i]->end)
{
if (j->end) j->end = min(k->down[i]->end, j->end);
else j->end = k->down[i]->end;
}
j->next = k->down[i];
p.push(q->down[i]);
}
else q->down[i] = k->down[i];
}
}
int getmother() { scanf("%s", S); root = new tire; return strlen(S); }
void work_out()
{
getnext();
tire *j = root, *u;
for (int i = 0, k, u = ans = 0; S[i]; i++)
{
k = S[i] - 'a';
j = j->down[k];
if (j->end)
{
u = min(u + 1, j->end - 1);
ans += u;
}
else { u++; ans += u; }
}
printf("Case #%d: %lld\n", ++t, ans);
}
};
ac_automaton f;
int main()
{
scanf("%d", &T);
while (T--)
{
int u = f.getmother();
scanf("%d", &n);
while (n--) f.insert();
f.work_out();
}
return 0;
}