今天写cf div3的B题，遇到一个统计子串个数的题：

http://codeforces.com/contest/977/problem/B

写一下题解：

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

map<string,int>mapt;

int cnt;

int find1(const std::string& str,const std::string& sub)
{
    int num = 0;
    for(int i = 0;(i = str.find(sub,i))!=std::string::npos;num++,i++);
    return num;
}
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i = 0;i<s.size()-1;i++)
    {
        string sub = s.substr(i,2);
        // cout<<sub<<endl;
        int index = 0;
        cnt = 0;
        mapt[sub] = find1(s,sub);
    }
    string ans_s;
    int ans = 0;
    for(auto t:mapt) 
    {
        if(ans<t.second) 
        {
            ans = t.second;
            ans_s = t.first;
        }
    }
    cout<<ans_s;
    return 0;
}

顺便总结一下模板：

子串可重叠情况：

int fun1(const std::string& str, const std::string& sub)
{
    int num = 0;
    for (size_t i = 0; (i = str.find(sub, i)) != std::string::npos; num++, i++);
    return num;
}

子串不可重叠情况：

int fun2(const std::string& str, const std::string& sub)
{
    int num = 0;
    size_t len = sub.length();
    if (len == 0)len=1;//应付空子串调用
    for (size_t i=0; (i=str.find(sub,i)) != std::string::npos; num++, i+=len);
    return num;
}