CodeForces - 883E Field of Wonders

Polycarpus takes part in the “Field of Wonders” TV show. The participants of the show have to guess a hidden word as fast as possible. Initially all the letters of the word are hidden.

The game consists of several turns. At each turn the participant tells a letter and the TV show host responds if there is such letter in the word or not. If there is such letter then the host reveals all such letters. For example, if the hidden word is “abacaba” and the player tells the letter “a”, the host will reveal letters at all positions, occupied by “a”: 1, 3, 5 and 7 (positions are numbered from left to right starting from 1).

Polycarpus knows m words of exactly the same length as the hidden word. The hidden word is also known to him and appears as one of these m words.

At current moment a number of turns have already been made and some letters (possibly zero) of the hidden word are already revealed. Previously Polycarp has told exactly the letters which are currently revealed.

It is Polycarpus’ turn. He wants to tell a letter in such a way, that the TV show host will assuredly reveal at least one more letter. Polycarpus cannot tell the letters, which are already revealed.

Your task is to help Polycarpus and find out the number of letters he can tell so that the show host will assuredly reveal at least one of the remaining letters.

Input
The first line contains one integer n (1 ≤ n ≤ 50) — the length of the hidden word.

The following line describes already revealed letters. It contains the string of length n, which consists of lowercase Latin letters and symbols ““. If there is a letter at some position, then this letter was already revealed. If the position contains symbol ““, then the letter at this position has not been revealed yet. It is guaranteed, that at least one letter is still closed.

The third line contains an integer m (1 ≤ m ≤ 1000) — the number of words of length n, which Polycarpus knows. The following m lines contain the words themselves — n-letter strings of lowercase Latin letters. All words are distinct.

It is guaranteed that the hidden word appears as one of the given m words. Before the current move Polycarp has told exactly the letters which are currently revealed.

Output
Output the single integer — the number of letters Polycarpus can tell so that the TV show host definitely reveals at least one more letter. It is possible that this number is zero.

Example
Input
4
a**d
2
abcd
acbd
Output
2
Input
5
lo*er
2
lover
loser
Output
0
Input
3
a*a
2
aaa
aba
Output
1
Note
In the first example Polycarpus can tell letters “b” and “c”, which assuredly will be revealed.

The second example contains no letters which can be told as it is not clear, which of the letters “v” or “s” is located at the third position of the hidden word.

In the third example Polycarpus exactly knows that the hidden word is “aba”, because in case it was “aaa”, then the second letter “a” would have already been revealed in one of previous turns.
题意描述：现在p去参加一个猜词比赛，他自己有一个题库，题库中保证一定有答案，他每次可以猜一个字母，问主持人答案中是否存在这个字母，答案中如果存在这个字母，那么这个字母的所有位置都会显现出来，但是他不会去猜不确定的字母，（因为题目要求每次他猜一个字母之后，主持人必须能揭晓一个或多个字母)，答案是不确定的，现在请你求出他所有能确定的字母的数目，在最终答案单词不确定的情况下，取这个数目的最小值。
思路：做这个题目首先要确定题库中的有效串，有两种情况题库中的串是无效的，第一种 看下面这组样例
4
a*cd
2
abcd
dddd
这样第二个串就是无效的，因为它跟已经显现的字母冲突了
第二种 看下面这组样例
4
a**d
2
abcd
aadd
这样第二个串也是无效的，因为答案中的a一定都显示出来了所以*的位置一定不可能再有a了，

看这样一组样例
4
a**d
2
abbd
abcd
这样答案是几？答案是1，虽然有可能确定出b c两个字母，但要求求最小值，所以答案是1
这样最后的答案就是再统计一下每个在题库中 答案串中是*位置 的字母，在所有有效串中共出现了几次（每个串出现多次，只统计一次），如果在所有有效串中都出现过了，那么就是可以确定的字母，因为p不会去猜不确定的字母，所以能确定的字母一定是在所有的有效串中都出现过，他才敢去猜，因为只有这样猜了之后才能每次至少揭晓一个。

code：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int len;
    cin>>len;
    string a;
    cin>>a;
    string b[1200];
    int m;
    cin>>m;
    for(int i=1; i<=m; i++)
        cin>>b[i];
    int book[200]= {0};
    int sset[100]= {0};//统计题库中所有在*位置出现的字母
    int adopt = 0;//统计有效串的个数
    for(int i=0; i<len; i++)
    {
        if(a[i]!='*')
        {
            int u = a[i]- 'a'+1;
            book[u] = 1;//统计在答案串中所有已经显现的字母
        }
    }
    int book2[2000]= {0};
    for(int i=1; i<=m; i++)
    {
        for(int j=0; j<len; j++)
        {
            if(a[j]=='*')
            {
                int u = b[i][j]-'a'+1;
                sset[u]++;
                if(book[u])
                {
                    book2[i] = 1;
                    break;
                }
            }
        }
    }

    for(int i=1; i<=m; i++)
    {
        for(int j=0; j<len; j++)
        {
            if(a[j]!='*')
            {
                if(b[i][j]!=a[j])
                {
                    book2[i]=1;
                    break;
                }
            }
        }
    }
    //以上是排除无效串，并将无效串在book2中设置为1
    for(int i=1; i<=m; i++)
    {
        if(!book2[i])
            adopt++;
    }
    int ss[2000][120]= {0};//统计每个串中*位置26个字母出现的次数
//    for(int i=1;i<=m;i++)
//        printf("%d ",book2[i]);
//    cout<<endl;

    for(int i=1; i<=m; i++)
    {
        if(!book2[i])
        {
            for(int j=0; j<len; j++)
            {
                if(a[j]=='*')
                {
                    int u = b[i][j]-'a'+1;
                    ss[i][u]++;
                }
            }
         //   cout<<ss[i][2]<<endl;
        }
    }
    int ss2[100]= {0};//统计26个字母分别在多少个有效串中出现过
    for(int i=1; i<=26; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(!book2[j])
            {
                if(ss[j][i]>=1)
                    ss2[i]++;
            }
        }
    }
    int sum = 0;
    //cout<<adopt<<endl;
    for(int i=1; i<=26; i++)
    {
        if(sset[i])
        {
            if(ss2[i]==adopt)//判断出现次数是否等于有效串个数
                sum++;
        }
    }
   // cout<<ss2[2]<<endl;
    cout<<sum<<endl;
    return 0;
}