『题解』BZOJ3172 [TJOI2013]单词

原文地址

Problem Portal

Portal1：BZOJ

Portal2：Luogu

Description

某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。

Input

第一个整数\(n\)，表示有多少个单词，接下来\(n\)行每行一个单词。每个单词由小写字母组成，\(n \leq 200\)，单词长度不超过\(10^{6}\)。

Output

输出\(n\)个整数，第\(i\)行的数字表示第\(i\)个单词在文章中出现了多少次。

Sample Input

3

a

aa

aaa

Sample Output

Solution

暴力出奇迹！

Source

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

using namespace std;

const int MAXN=205;

int n;

string st[MAXN];

int main() {

    scanf("%d",&n);

    for (int i=1; i<=n; i++)

        cin >> st[i];

    for (int i=1; i<=n; i++) {

        int ans=0;

        for (int j=1; j<=n; j++)

            if (j!=i) {//每次都暴力找一遍

                int last=0, k=st[j].find(st[i], last);

                while (~k) {

                    last=k+1;

                    k=st[j].find(st[i], last);

                    ans++;

                }

            }

        printf("%d\n",++ans);//要加上自己的那个

    }

    return 0;

}

巴特西