redis启动

cmd-

redis-server.exe (redis.windows.conf)
第二个参数可以写也可以不写

开启

redis-cli.exe -h 127.0.0.1 -p 6379

Java-SpringBoot使用Redis

RedisConfig

其中Bean代表由Spring管理,当Resouorce的name和Bean的name一样时,就会自动通过Bean创建实例.
@Value的字段是在application.properties中,有’.’的话要加${}
这里调用的只是Redis的一个构造函数,传入ip和端口号.

package com.mall.concurrency.cache;

import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

import redis.clients.jedis.JedisPool;

@Configuration
public class RedisConfig {

    @Bean(name="redisPool")
    public JedisPool jedispool(@Value("{jedis.host}") String host,@Value("{jedis.port}") int port){
        return new JedisPool(host,port);
    }
}

RedisClient

类似于Orm的操作方式.用完即扔.

package com.mall.concurrency.cache;

import javax.annotation.Resource;

import org.springframework.stereotype.Component;

import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;

//http://redis.cn/
@Component
public class RedisClient {
    @Resource(name="redisPool")
    private JedisPool jedisPool;

    public void set(String key,String value)throws Exception{
        Jedis jedis=null;
        try{
            jedis = jedisPool.getResource();
            jedis.set(key, value);
        }finally {
            if(jedis!=null){
                jedis.close();
            }
        }
    }

    public String get(String key)throws Exception{
        Jedis jedis=null;
        try{
            jedis = jedisPool.getResource();
            return jedis.get(key);
        }finally {
            if(jedis!=null){
                jedis.close();
            }
        }
    }
}

CacheController

其中@Autowired和@Resource的区别是:
– @Resource默认按照名称方式进行bean匹配,@Autowired默认按照类型方式进行bean匹配
– @Resource(import javax.annotation.Resource;)是J2EE的注解,@Autowired( import org.springframework.beans.factory.annotation.Autowired;)是Spring的注解

package com.mall.concurrency.cache;

import javax.annotation.Resource;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.ResponseBody;

@Controller
@RequestMapping("/cache")
public class CacheController {
    @Autowired
    private RedisClient redisClient;

    @RequestMapping("/set")
    @ResponseBody
    public String set(@RequestParam("k") String k,@RequestParam("v") String v)throws Exception{
        redisClient.set(k, v);
        return "SUCCESS";
    }

    @RequestMapping("/get")
    @ResponseBody
    public String get(@RequestParam("k") String k)throws Exception{
        return redisClient.get(k);
    }

}

application.properties的书写格式

# redis
jedis.host=127.0.0.1
jedis.port=6379

DotNet

SQL:
工厂模式创建DbCommand
    /// <summary>
    /// 创建新的连接对象
    /// </summary>
    /// <returns></returns>
    public static DbCommand CreateCommand()
    {
        string dataProviderName = BalloonShopConfiguration.DbProviderName;
        string connectionString = BalloonShopConfiguration.DbConnectionString;
        ///工厂模式下新建名字为dataProviderName的连接
        DbProviderFactory factory = DbProviderFactories.GetFactory(dataProviderName);
        DbConnection conn = factory.CreateConnection();
        ///项数据工厂设置连接字符串
        conn.ConnectionString = connectionString;
        ///创建特定于某数据库的command对象
        DbCommand comm = conn.CreateCommand();
        comm.CommandType = CommandType.StoredProcedure;
        return comm;
    }

执行查询:
    /// <summary>
    /// 执行查询语句
    /// </summary>
    /// <param name="command"></param>
    /// <returns></returns>
    public static DataTable ExecuteSelectCommand(DbCommand command)
    {
        ///将返回的Datatable
        DataTable table;
        try
        {
            //执行该命令
            command.Connection.Open();
            DbDataReader dr = command.ExecuteReader();
            table = new DataTable();
            table.Load(dr);
            dr.Close();
        }
        catch (Exception e)
        {
            Utilities.LogError(e);
            throw;
        }
        finally
        {
            command.Connection.Close();
        }
        return table;
    }

返回Datatable是因为可以使用更少的时间

51nod 1158

Type:悬线法,单调栈(未学,用悬线法做的)

提示

蓝书P51,最大子矩阵 O(mn)

Code

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=510;
int m,n;
int mat[maxn][maxn],up[maxn][maxn],left[maxn][maxn],right[maxn][maxn];

void print(){
    printf("Up:\n");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",up[i][j]);
        }
        puts("");
    }
    printf("Left:\n");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",left[i][j]);
        }
        puts("");
    }
    printf("Right:\n");
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",right[i][j]);
        }
        puts("");
    }
}

int main(){
    while(~scanf("%d%d",&m,&n)){
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                scanf("%d",&mat[i][j]);
            }
        }
        int ans=0;
        for(int i=1;i<=m;++i){
            int lo=0,ro=n;
            for(int j=1;j<=n;++j){///从右往左扫描,维护up和left
                if(!mat[i][j]){
                    up[i][j]=left[i][j]=0;lo=j;
                }else{
                    up[i][j]=up[i-1][j]+1;
                    left[i][j]=max(left[i-1][j],lo+1);
                }
            }
            for(int j=n;j>=1;--j){///维护right
                if(!mat[i][j]){
                    right[i][j]=n+1;ro=j-1;
                }else{
                    right[i][j]=i==1?ro:min(right[i-1][j],ro);
                    ans=max(ans,up[i][j]*(right[i][j]-left[i][j]+1));
                }
            }
        }
        //print();
        printf("%d\n",ans);
    }
    return 0;
}

三角函数+公式推导+部分C++函数

两角和的公式

  sin(A+B)=sinAcosB+cosAsinB sin(A-B)=sinAcosB-sinBcosA

  cos(A+B)=cosAcosB-sinAsinB cos(A-B)=cosAcosB+sinAsinB

  tan(A+B)=(tanA+tanB)/(1-tanAtanB) tan(A-B)=(tanA-tanB)/(1+tanAtanB)

  cot(A+B)=(cotAcotB-1)/(cotB+cotA) cot(A-B)=(cotAcotB+1)/(cotB-cotA)

  倍角的公式

  tan2A=2tanA/(1-tan2A) cot2A=(cot2A-1)/2cota

  cos2a=cos2a-sin2a=2cos2a-1=1-2sin2a

  sinα+sin(α+2π/n)+sin(α+2π*2/n)+sin(α+2π*3/n)+……+sin[α+2π*(n-1)/n]=0

  cosα+cos(α+2π/n)+cos(α+2π*2/n)+cos(α+2π*3/n)+……+cos[α+2π*(n-1)/n]=0 以及

  sin^2(α)+sin^2(α-2π/3)+sin^2(α+2π/3)=3/2

  tanAtanBtan(A+B)+tanA+tanB-tan(A+B)=0

  四倍角之公式:

  sin4A=-4*(cosA*sinA*(2*sinA^2-1))

  cos4A=1+(-8*cosA^2+8*cosA^4)

  tan4A=(4*tanA-4*tanA^3)/(1-6*tanA^2+tanA^4)

  五倍将式:

  sin5A=16sinA^5-20sinA^3+5sinA

  cos5A=16cosA^5-20cosA^3+5cosA

  tan5A=tanA*(5-10*tanA^2+tanA^4)/(1-10*tanA^2+5*tanA^4)

  六倍将式:

  sin6A=2*(cosA*sinA*(2*sinA+1)*(2*sinA-1)*(-3+4*sinA^2))

  cos6A=((-1+2*cosA^2)*(16*cosA^4-16*cosA^2+1))

  tan6A=(-6*tanA+20*tanA^3-6*tanA^5)/(-1+15*tanA^2-15*tanA^4+tanA^6)

  七倍将式:

  sin7A=-(sinA*(56*sinA^2-112*sinA^4-7+64*sinA^6))

  cos7A=(cosA*(56*cosA^2-112*cosA^4+64*cosA^6-7))

  tan7A=tanA*(-7+35*tanA^2-21*tanA^4+tanA^6)/(-1+21*tanA^2-35*tanA^4+7*tanA^6)

  八倍将式:

  sin8A=-8*(cosA*sinA*(2*sinA^2-1)*(-8*sinA^2+8*sinA^4+1))

  cos8A=1+(160*cosA^4-256*cosA^6+128*cosA^8-32*cosA^2)

  tan8A=-8*tanA*(-1+7*tanA^2-7*tanA^4+tanA^6)/(1-28*tanA^2+70*tanA^4-28*tanA^6+tanA^8)

  九倍将式:

  sin9A=(sinA*(-3+4*sinA^2)*(64*sinA^6-96*sinA^4+36*sinA^2-3))

  cos9A=(cosA*(-3+4*cosA^2)*(64*cosA^6-96*cosA^4+36*cosA^2-3))

  tan9A=tanA*(9-84*tanA^2+126*tanA^4-36*tanA^6+tanA^8)/(1-36*tanA^2+126*tanA^4-84*tanA^6+9*tanA^8)

  十倍将式:

  sin10A=2*(cosA*sinA*(4*sinA^2+2*sinA-1)*(4*sinA^2-2*sinA-1)*(-20*sinA^2+5+16*sinA^4))

  cos10A=((-1+2*cosA^2)*(256*cosA^8-512*cosA^6+304*cosA^4-48*cosA^2+1))

  tan10A=-2*tanA*(5-60*tanA^2+126*tanA^4-60*tanA^6+5*tanA^8)/(-1+45*tanA^2-210*tanA^4+210*tanA^6-45*tanA^8+tanA^10)

  ·万能公式:

  sinα=2tan(α/2)/[1+tan^2(α/2)]

  cosα=[1-tan^2(α/2)]/[1+tan^2(α/2)]

  tanα=2tan(α/2)/[1-tan^2(α/2)]

  半将式

  sin(A/2)=√((1-cosA)/2) sin(A/2)=-√((1-cosA)/2)

  cos(A/2)=√((1+cosA)/2) cos(A/2)=-√((1+cosA)/2)

  tan(A/2)=√((1-cosA)/((1+cosA)) tan(A/2)=-√((1-cosA)/((1+cosA))

  cot(A/2)=√((1+cosA)/((1-cosA)) cot(A/2)=-√((1+cosA)/((1-cosA))

  和差化积

  2sinAcosB=sin(A+B)+sin(A-B) 2cosAsinB=sin(A+B)-sin(A-B)

  2cosAcosB=cos(A+B)-sin(A-B) -2sinAsinB=cos(A+B)-cos(A-B)

  sinA+sinB=2sin((A+B)/2)cos((A-B)/2 cosA+cosB=2cos((A+B)/2)sin((A-B)/2)

  tanA+tanB=sin(A+B)/cosAcosB tanA-tanB=sin(A-B)/cosAcosB

  cotA+cotBsin(A+B)/sinAsinB -cotA+cotBsin(A+B)/sinAsinB

  某些数列前n项和

  1+2+3+4+5+6+7+8+9+…+n=n(n+1)/2 1+3+5+7+9+11+13+15+…+(2n-1)=n2

  2+4+6+8+10+12+14+…+(2n)=n(n+1) 1^2+2^2+3^2+4^2+5^2+6^2+7^2+8^2+…+n^2=n(n+1)(2n+1)/6

  1^3+2^3+3^3+4^3+5^3+6^3+…n^3=(n(n+1)/2)^2 1*2+2*3+3*4+4*5+5*6+6*7+…+n(n+1)=n(n+1)(n+2)/3

  正弦定理 a/sinA=b/sinB=c/sinC=2R 注: 其中 R 表示三角形的外接圆半径

  余弦定理 b2=a2+c2-2accosB 注:角B是边a和边c的夹角

  乘法与因式分 a2-b2=(a+b)(a-b) a3+b3=(a+b)(a2-ab+b2) a3-b3=(a-b(a2+ab+b2)

  三角不等式 |a+b|≤|a|+|b| |a-b|≤|a|+|b| |a|≤b<=>-b≤a≤b

  |a-b|≥|a|-|b| -|a|≤a≤|a|

推论

三角形ABC中: tan(a/2)tan(b/2)+tan(b/2)tan(c/2)+tan(a/2)tan(c/2)=1

S(ABC)=[1/2(a+b+c)]r(△ABC内接圆半径)

三角形ABC中: 设 1/2周长为 p=1/2(a+b+c) 
            tan(a/2)=r/(p-b)

动态规划

痛并不快乐着..

数位dp

HDU 3555

不要49

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL dp[20][3];
int digit[20];

LL dfs(int pos,int pre,int state,bool jud){
    //cout<<pos<<" "<<state<<endl;
    ///数位递归到0则返回
    if(pos==0)
        return 1;
    ///如果有数据就返回数据
    if(!jud&&dp[pos][state]!=-1)
        return dp[pos][state];

    LL ans=0;
    int ed=jud?digit[pos]:9;
    //cout<<ed<<endl;
    for(int i=0;i<=ed;++i){
        if(pre==4&&i==9)continue;
        ans+=dfs(pos-1,i,i==4,jud&&i==ed);
    }
    if(!jud){///不取上界时,可以取满
        dp[pos][state]=ans;
    }
    return ans;
}

///数字处理函数
LL cal(LL x){
    int pos=0;
    while(x){
        digit[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,0,0,true);
}

int main(){
    memset(dp,-1,sizeof(dp));
    int T;
    for(scanf("%d",&T);T;T--){
        LL n;
        scanf("%lld",&n);
        printf("%lld\n",n-cal(n)+1);
    }
    return 0;
}

HDU 2089

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1000000+7;
LL dp[20][3];
int digit[20];

LL dfs(int pos,int pre,int state,bool jud){
    //cout<<pos<<" "<<state<<endl;
    ///数位递归到0则返回
    if(pos==0)
        return 1;
    ///如果有数据就返回数据
    if(!jud&&dp[pos][state]!=-1)
        return dp[pos][state];

    LL ans=0;
    int ed=jud?digit[pos]:9;//这句是判断他的上界
    //cout<<ed<<endl;
    for(int i=0;i<=ed;++i){
        if(pre==6&&i==2)continue;
        if(i==4)continue;
        ans+=dfs(pos-1,i,i==6,jud&&i==ed);
    }
    if(!jud){///不取上界时,可以取满
        dp[pos][state]=ans;
    }
    return ans;
}

///数字处理函数
LL cal(LL x){
    int pos=0;
    //cout<<"tx: ";
    while(x){
        digit[++pos]=x%10;
        //cout<<x%10<<endl;
        x/=10;
    }
    return dfs(pos,0,0,true);
}

int main(){
    memset(dp,-1,sizeof(dp));
    LL n,m;
    while(~scanf("%lld%lld",&n,&m) && n+m){
        printf("%lld\n",cal(m)-cal(n-1));
    }
    return 0;
}

UVa 11021

Type: 概率

题解

有点难以理解题解的递推式,把那句f(i-1)表示i-1天后全部死亡改成f(i-1)表示i-1天后一个不生的概率可能更好理解一点吧

不知道怎么证明这个式子,思维还是不强

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;

double f[maxn],P[maxn];;
int n,k,m,T;

int main(){
    cin>>T;
    for(int i=1;i<=T;++i){
        cin>>n>>k>>m;
        for(int j=0;j<n;++j) cin>>P[j];
        f[0]=0;f[1]=P[0];
        for(int j=2;j<=m;++j){
            f[j]=0;
            for(int t=0;t<n;++t){
                f[j]+=(P[t]*pow(f[j-1],t));
            }
        }
        printf("Case #%d: %.7lf\n",i,pow(f[m],k));
    }
    return 0;
}

51nod 1225 余数之和

Type:逆元,数论,思维,同余定理

直接上代码,题解在代码中,这道题有点耗时间,但挺有趣的

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL N;
/*打表
void Table(int NN){
    for(int i=1;i<=NN;++i){
        printf("%04d-%04d ",i,NN%i);
    }
}
*/
LL fast_mod(LL a,LL n,LL Mod){
    LL ans=1;
    while(n){
        if(n&1){
            ans=(ans*a)%Mod;
        }
        a=(a*a)%Mod;
        n>>=1;
    }
    return ans;
}

LL inv2=fast_mod(2,mod-2,mod);
///对照算法
LL hh(){
    LL n=N;
    LL ans;
    ans=n%mod*(n%mod)%mod;
    for(LL t,r,i=1;i<=n;++i) {
        t=n/i;
        r=n/t;
        ans=ans-((r-i+1)%mod*((r+i)%mod))%mod*inv2%mod*t%mod;
        while(ans<0) ans+=mod;
        i=r;
    }
    return ans;
}

///本来想的是计算当前N/i相同的数量--结果为:
///(N-tmp*i)/i 即计算在 N-当前数字*(N/i)后还有多少个数字可以
///整分给(N/i),由于这个方法利用了除法,所以处理除法溢出有点麻烦
///1e9左右就炸掉了
///乘法溢出也很麻烦

///最好的方法就是 N/tmp 理解为最后一个除以 N 等于 tmp 的数字是几

///式子: F[N]=N*N-Sigma(N/i*i | i∈[1,N])
///其中 括号内的式子的 N/i 有sqrt(n)个不同的值
///证: 设 tmp=100/i 则 tmp*i=100 故 Count(tmp)<=sqrt(100)
///并且可以看出 相同的 N/i 对应的 i 是连续的.
///即我们可以用等差数列求和公式来求 当 tmp=N/i 时 i 的和
///用等差数列求和时/2用 2的逆元来做\

///自己坐着坐着就莫名其妙和他一样了= =
LL solve(){
    LL ans=N%mod*(N%mod)%mod;
    for(LL i=1;i<=N;){
        LL tmp=N/i;
        LL t=N/tmp;
        tmp=((i+t)%mod*((t-i+1)%mod))%mod*inv2%mod*tmp%mod;
        ans=(ans%mod-tmp%mod+mod)%mod;
        i=t+1;
    }
    return ans;
}

void dui_pai(){
    for(LL i=1;i<=1000000;++i){
        N=i;
        if(hh()!=solve()) printf("%lld Faild\n",N);
    }
    puts("Done");
}

int main(){
    //dui_pai();
    while(~scanf("%lld",&N)){
        printf("%lld\n",solve());
    }
    return 0;
}

LA 4670

Type:AC自动机

题意

给你一堆子串和一个主串

问你在主串中出现次数最多的子串有哪些,最后结果按字典序排列

Code

#include<bits/stdc++.h>
using namespace std;

const int maxn=11000;
const int maxm=152;
const int maxt=1e6+6;

int T,N,tot_len;
char str[maxm][80],tot[maxt];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cnt[maxn],val[maxn];
    bool vis[maxn][sigma_size];

    int siz,root,max_time;

    vector<string> ans;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        for(int i=0;i<sigma_size;++i){
            vis[siz][i]=false;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        ans.clear();
        for(int i=0;i<maxn;++i) val[i]=cnt[i]=0;
        siz=0;root=0;max_time=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s,int v){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]=v;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];

            int p=u;
            //cout<<i<<"  "<<u<<": "<<c<<endl;
            ///while是用来判断子串的.这道题不需要加
            while(p && val[p]){
                if(!vis[p][c]){
                    cnt[val[p]]++;
                    max_time=max(cnt[val[p]],max_time);
                    p=f[p];
                    vis[p][c]=true;
                }
            }
        }
    }

    void print(){
        printf("%d\n",max_time);
        for(int i=1;i<=N;++i){
            if(cnt[i]==max_time){
                ans.push_back(str[i]);
            }
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();++i){
            cout<<ans[i]<<endl;
        }
    }
}aho;

int main(){
    while(~scanf("%d",&N) && N){
        aho.init();
        for(int i=1;i<=N;++i){
            scanf("%s",str[i]);
            aho.insert(str[i],i);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        //scanf("%[^\n]",str);
        gets(tot);
        tot_len=strlen(tot);
        //cout<<tot_len<<endl;
        aho.Find(tot);
        aho.print();
    }
    return 0;
}

HDU 5880

Type: AC自动机

题意

给你N个子串,一个主串,让你过滤掉在主串中出现过的子串.被过滤掉的用*表示

每个子串是由小写字母组成

题解

AC自动机,一开始被两个样例卡住了

1- 子串: abcd bc 主串: abcef 匹配不到 bc
2- 子串: a ab abc abcd 主串: aabcd 匹配不到 abcd

第一种情况是因为当你遍历到abcd这条路径的c节点时,如果因为下一个是f就判断为失配并且不继续向下走,则就无法再匹配到bc.

解决方法,在每次判断到失配的时候,新开一个函数从开始失配的节点 这里是 c ,从这个节点开始找他的失陪路径,知道找到 第一个尾节点 或 根节点 就停止,目标串即为最长被匹配串,不需要再去匹配他的子串了.

第二种情况是因为一开始写代码每次循环时直接将u查找到了根节点,所以如果一个子串前面是另一个串的子串,那么将永远无法匹配到另一个子串.

解决方法,不改动u,借助临时变量来更改u达到查找子串的目的.

Code

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000000+6;

int T,N,tot_len;
char str[maxn],len[maxn];

struct AC_AutoMaton{
    static const int sigma_size=26;

    int ch[maxn][sigma_size];

    int f[maxn];

    int cle[maxn],val[maxn];

    int siz,root;

    int newNode(){
        for(int i=0;i<sigma_size;++i){
            ch[siz][i]=0;
        }
        f[siz]=val[siz]=0;
        return siz++;
    }

    void init(){
        for(int i=0;i<maxn;++i) val[i]=0;

        siz=0;root=0;
        newNode();
    }

    int ord(char c){
        if(isupper(c))
            c=tolower(c);
        return (int)(c-'a');
    }

    void insert(char *s,int v){
        int u=root,n=strlen(s);
        for(int i=0;i<n;++i){
            int c=ord(s[i]);
            if(!ch[u][c]) ch[u][c]=newNode();
            u=ch[u][c];
       }
       val[u]=v;
    }

    void getFail(){
        queue<int> Q;
        Q.push(root);
        while(!Q.empty()){
            int k=Q.front();
            Q.pop();
            for(int c=0;c<sigma_size;++c){
                if(ch[k][c]){
                    f[ch[k][c]]=k?ch[f[k]][c]:0;
                    Q.push(ch[k][c]);
                }
                else ch[k][c]=ch[f[k]][c];
            }
        }
    }

    void add(int u,int i){
        while(u){
            if(val[u]){
                int t=len[val[u]];
                for(int r=0;r<t;++r){
                    cle[i-r]=1;
                }
                return;
            }
            u=f[u];
        }
    }

    void Find(char *s){
        int u=0,n=tot_len;
        for(int i=0;i<tot_len;++i) cle[i]=0;
        for(int i=0;i<n;++i){
            if(!isalpha(s[i])){
                u=0;
                continue;
            }
            int c=ord(s[i]);
            ///下面这句加不加都一样
            //while(u && !ch[u][c]) u=f[u];
            u=ch[u][c];
            /*
            int p=u;
            //cout<<i<<"  "<<u<<": "<<c<<endl;
            ///while是用来判断子串的.这道题不需要加
            while(p && val[p]){
                p=f[p];
            }
            */
            add(u,i);
        }
    }

    void print(){
        for(int i=0;i<tot_len;++i){
            if(cle[i]) putchar('*');
            else putchar(str[i]);
        }
        printf("\n");
    }
}aho;

int main(){
    scanf("%d",&T);
    while(T--){
        aho.init();
        scanf("%d",&N);
        for(int i=0;i<N;++i){
            scanf("%s",str);
            aho.insert(str,i+1);
            len[i+1]=strlen(str);
        }
        getchar();
        aho.getFail();
        tot_len=0;
        //scanf("%[^\n]",str);
        gets(str);
        tot_len=strlen(str);
        //cout<<tot_len<<endl;
        aho.Find(str);
        aho.print();
    }
    return 0;
}