toj 2806 Replace Words

Time Limit: 1.0 Seconds Memory Limit: 65536K
Total Runs: 476 Accepted Runs: 172 Multiple test files

The text editors such as notepad, Microsoft Word, all have a very useful tool in edit menu, that is "replace", which you can press a shortcut key "ctrl+H" to open. It can help us when we want to replace all of certain set of words with another set of words in our text files.

Now the task coming to us is to write a program for simulating this "Replace" function.

Input

For each test case, the first line contains the word(s) to be replaced (consist of 100 characters at most), the second line contains the new word(s) (consist of 100 characters at most). Please note both lines may contain blank spaces. Then following lines are all text contents till the end of file. For each line, it consists of 1000 characters at most.

Output

Output the new text contents after you have replaced all the words. The format of new text contents is the same as text contents shown in input.

Sample Input

Tianjin University TJU Brief Introduction -------------------------------------------------------------------------------- Vision Tianjin University aspires to be a world-class, progressive, and multidisciplina ry research university. Mission Tianjin University is committed to - Advancing knowledge - Bringing knowledge to industry for social development - Collaborating with leading institutions and organizations - Developing quality education combined with rigorous academic research Motto Seeking Truth from Facts Guideline Precise in Learning, Strict in Teaching Focus Engineering integrated with Science, Liberal Arts, Business, Law, etc.

Sample Output

Brief Introduction -------------------------------------------------------------------------------- Vision TJU aspires to be a world-class, progressive, and multidisciplina ry research university. Mission TJU is committed to - Advancing knowledge - Bringing knowledge to industry for social development - Collaborating with leading institutions and organizations - Developing quality education combined with rigorous academic research Motto Seeking Truth from Facts Guideline Precise in Learning, Strict in Teaching Focus Engineering integrated with Science, Liberal Arts, Business, Law, etc.

Problem Setter: tashj (blog: http://tashj.yculblog.com)

Source: TJU Programming Contest 2007 Preliminary

Submit List Runs Forum Statistics

//注意这个KMP是用字符数组,并且它是从字符数组的0下标开始用的
//638970 2009-05-16 09:36:08 Accepted 2806 C++ 1.3K 0'00.00" 2188K forever4444
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1003;
char str[N][N];
char red[104], T[104];
int next[103], Tlen, Slen;

void get_next()  //计算模式串t的next函数值,存入数组next中
{
    int j, k;

    j = 0; k = -1; next[0] = -1;

    while(j < Tlen)  //Tlen是要匹配的模式串的长度
        if(k == -1 || T[j] == T[k])
            next[++j] = ++k;
        else
            k = next[k];
}

int index_KMP(int pos, int cc)  //在目标串S中找模式串T首次出现的位置,若不存在则返回-1
{
    int i, j;
    i = pos ; j = 0;

    while(i < Slen && j < Tlen)
        if(j == -1 || str[cc][i] == T[j])
        {
            i++; j++;
        }
        else
            j = next[j];
    if(j == Tlen)   //证明查找成功了
        return i - Tlen;
    else   //没有查找成功
        return -1;

}

int main()
{
    int cnt = 0;
    int i, j, k, kk;
    gets(T);
    gets(red);

    Tlen = strlen(T);

    while(gets(str[cnt++]));
    get_next();

    for(i = 0; i < cnt - 1; i++) //对str中每一行进行查找
    {
        Slen = strlen(str[i]);  //求出每一行的长度
        for(j = 0; j < Slen; j++)   //进行模式匹配
        {
            k = index_KMP(j, i);
            if(k == -1)   //没有找到
            {
                printf("%s", str[i] + j);
                  break;
            }
            else
            {
                for(kk = j; kk < k; kk++)
                    printf("%c", str[i][kk]);
                printf("%s", red);
                j = k + Tlen - 1;
            }
        }
        putchar('\n');
    }

    return 0;
}

//附上我们的KMP省赛模板

KMP
假设主串：s: ‘s(1)  s(2)  s(3) ……s(n)’ ;   模式串：p: ‘p(1)  p(2)  p(3)…..p(m)’
现在我们假设主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k<j)个字符继续比较
此时，s(i)≠p(j),  有
主串：               S(1)……  s(i-j+1)…… s(i-1)   s(i) ………….
                                || (相配)   ||       ≠(失配)
匹配串：                        P(1) …….  p(j-1)   p(j)
由此，得到关系式
          ‘p(1)  p(2)  p(3)…..p(j-1)’   =    ’ s(i-j+1)……s(i-1)’
由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在  k’>k  满足下列关系式：(k<j),
          ‘p(1)  p(2)  p(3)…..p(k-1)’   =    ’ s(i-k+1)s(i-k+2)……s(i-1)’
即：
主串：        S(1)……s(i-k +1) s(i-k +2) ……s(i-1)     s(i) ………….
                        || (相配)  ||           ||       ?(有待比较)
匹配串：                P(1)      p(2)    …… p(k-1)    p(k)
现在把前面总结的关系综合一下
S(1)…s(i-j +1)…  s(i-k +1) s(i-k +2)  ……    s(i-1)     s(i) ……
           || (相配)  ||         ||               ||         ≠(失配)
           P(1) ……p(j-k+1)   p(j-k+2)  …

.   p(j-1)    p(j)
                      || (相配)  ||               ||          ?(有待比较)
                      P(1)       p(2)    …….    p(k-1)      p(k)

由上，我们得到关系：
‘p(1)  p(2)  p(3)…..p(k-1)’   =    ’ s(j-k+1)s(j-k+2)……s(j-1)’
接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)
K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10004;
const int M = 1000005;

char S[N],//主串
     T[M];//模式串
int Slen, Tlen;//主串和模式串的长度
int next[M];

void Get_next()
{
    int j, k;

    j = 0; k = -1; next[0] = -1;

    while(j < Tlen)
        if(k == -1 || T[j] == T[k])
        {
            next[++j] = ++k;
        }
        else
            k = next[k];

}
int KMP_Count()
{//此函数用于计算模式串在主串中出现的次数，可以交叉
    int ans = 0;
    int i, j = 0;
    Slen = strlen(S);
    Tlen = strlen(T);
    if(Slen == 1 && Tlen == 1)  //主串和模式串长度均为1的情况
    {
        if(S[0] == T[0])
            return 1;
        else
            return 0;
    }
    Get_next();

    for(i = 0; i < Tlen; i++)
    {
        while(j > 0 && S[j] != T[i])
            j = next[j];
        if(S[j] == T[i])
            j++;
        if(j == Slen)
        {
            ans++;
            j = next[j];
        }
    }
    return ans;
}

int KMP_Index()
{//此函数用于返回模式串在主串中第一次出现的位置
//不存在返回-1
    int i, j;
    i = j = 0;

    Slen = strlen(S); Tlen = strlen(T);
    Get_next();

    while(i < Slen && j < Tlen)
        if(j == -1 || S[i] == T[j])
        {
            i++; j++;
        }
        else
            j = next[j];

    if(j == Tlen)   //返回第一次出现的位置
        return i - Tlen;
    else
        return -1;

}

int main()
{
    int n;
    scanf("%d", &n);
    getchar();
    while(n--)
    {
        scanf("%s%s", S, T);//输入主串和模式串
        printf("%d\n", KMP_Count());
    }
    return 0;
}