子串计算

import java.util.ArrayList;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		String line;
		while (input.hasNextLine()) {
			line = input.nextLine();
			parse(line);
		}
	}
	private static void parse(String line) {
		String subLine;
		Map<String, Integer> map = new TreeMap<String, Integer>();
		ArrayList<String> list = new ArrayList<String>();
		for (int i = 0; i < line.length(); i++) {
			for (int j = i + 1; j <= line.length(); j++) {
				subLine = line.substring(i, j);
				if (subLine.length() != line.length()) {
					list.add(subLine);
					map.put(subLine, 0);
				}
			}
		}
	    for (int i = 0; i < list.size(); i++) {
			for (Map.Entry<String, Integer> entry : map.entrySet()) {
				if (list.get(i).equals(entry.getKey())) {
					entry.setValue(entry.getValue() + 1);
				}
			}
		}
		for (Map.Entry<String, Integer> entry : map.entrySet()) {
			if (entry.getValue() > 1) {
				System.out.print(entry.getKey() + " " + entry.getValue());
				System.out.println();
			}
		}
	}
}

#!/usr/bin/python
#-*- coding:utf-8 -*-

#Author: Ben

class Node:
    def __init__(self):
        self.left = self.right = None
        self.freq = 0

class Trie:
    def __init__(self):
        self.root = Node()

    def add(self, word):
        node = self.root
        for ch in word:
            if ch == '0':
                if node.left == None:
                    node.left = Node()
                node = node.left
            else:
                if node.right == None:
                    node.right = Node()
                node = node.right
            node.freq += 1

def preOrder(node, s):
    if node:
        if node.freq > 1:
            print "%s %d" % (s, node.freq)
        preOrder(node.left, s+'0')
        preOrder(node.right, s+'1')

while True:
    try:
        s = raw_input()
        tree = Trie()
        l = len(s)
        for i in range(l):
            tree.add(s[i:l])
        preOrder(tree.root, '')
    except:
        break 

#include<iostream>
#include<string.h>
using namespace std;
struct Part//子串结构体
{
     string s;//子串
     int num;//出现次数
};
int find_part(string r,string p)//返回子串在总串的出现次数
{
    int len1=r.size(),len2=p.size(),c=0;
    if(len1<len2)
        return 0;
    else if(len1==len2 && p==r)
        return 1;
    else
    {
        for(int i=0;i<len2;i++)//注意这里是从0到子串的长度
        {
            for(int j=i;j<len1;j+=len2)
            {
                string temp;
                for(int k=j;k<j+len2;k++)
                    temp+=r[k];
                if(temp==p)
                    c++;
            }
        }
        return c;
    }
}

bool judge(Part ss[],int n,string p)//判断子串是否出现过
{
    for(int i=0;i<n;i++)
        if(ss[i].s==p)
            return false;
    return true;
}

int main()
{
    string r;
    while(cin>>r)
    {
        int len=r.size(),index=0;
        Part p[100];
        for(int i=0;i<len;i++)
        {
            for(int j=i;j<len;j++)
            {
                string temp;
                for(int k=i;k<=j;k++)
                    temp+=r[k];
                if(index==0 && find_part(r,temp)>1)
                {
                    p[0].s=temp;
                    p[0].num=find_part(r,temp);
                    index++;
                }
                else if(index!=0 && judge(p,index,temp) && find_part(r,temp)>1)
                {
                    p[index].s=temp;
                    p[index].num=find_part(r,temp);
                    index++;
                }
            }
        }
        for(int i=0;i<index;i++)//冒泡排序
        {
            for(int j=1;j<index;j++)
            {
                Part temp;
                if(p[j].s<p[j-1].s)
                {
                    temp=p[j-1];
                    p[j-1]=p[j];
                    p[j]=temp;
                }
            }
        }
        for(int i=0;i<index;i++)
            cout<<p[i].s<<" "<<p[i].num<<endl;
    }
    return 0;
}

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        //获得子串
        set<string> sets; //使用set可以自动排序
        for(int i=0;i<s.length();i++){
            for(int j=i;j<s.length();j++){
                sets.insert(s.substr(i,j-i+1));
            }
        }
        //统计数量
        for(auto it=sets.begin();it!=sets.end();++it){
            int count=0,k=0;
            while(k<s.length()){
                int f=s.find(*it,k);
                if(f>=0){
                    count++;
                    k=f+1;
                }else
                    break;
            }
            //输出
            if(count>=2){
                cout<<*it<<" "<<count<<endl;
            }
        }
    }
    return 0;
}

#include <iostream>
#include <set>
#include <string>

using namespace std;

int main() {
    string str;
    while(cin>>str) {
        /* 得到所有子串 */
        set<string> s;
        for(int i=0;i<str.size();i++) {
            for(int j=i;j<str.size();j++) {
                s.insert(str.substr(i,j-i+1));
            }
        }
        for(set<string>::iterator it=s.begin();it!=s.end();it++) {
            int count=0,pos=0,res=0,j=0;
            while(j<str.size()) {
                res=str.find(*it,j);
                if(res!=string::npos) {
                    count++;
                    j=res+1;
                } else {
                    break;
                }
            }
            if(count>=2) {
                cout<<*it<<" "<<count<<endl;
            }
        }
    } 
    return 0;
} 

//map功能太强大了，如果面试不提供这个库，立马就GG了
#include<iostream>
using namespace std;
#include<string>
#include<map>

int main() {
	string s;
	while (cin >> s) {
		map<string, int> m;
		for (int i = 0;i<=s.size();i++) 
			for (int j = 0;j<i;j++) 
				m[s.substr(j,i-j)]++;
        
		for (auto it = m.begin();it != m.end();it++) {
			if (it->second > 1)
				cout << it->first << ' ' << it->second << endl;
		}
		
	}
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 5050
#define LEN 101
using namespace std;

struct STR{
    char s[LEN];
    unsigned count;
}buf[N];//子串集合
int n;//子串的数量
char str[LEN];//读取的字符串
char child[LEN];//临时存储子串

void MakeChild(int from, int len)
{//读取字符串中的子串，存入child字符串。子串从from开始，长度为len
    for(int i=0; i<len; i++)
    {
        child[i]=str[from+i];
    }
    child[len]='\0';
}

bool cmp(STR a, STR b)
{
    return strcmp(a.s, b.s)<0;
}

void LetsGo()//生成子串列表并完成统计
{
    int len=strlen(str);
    for(int i=1; i<len; i++)//i是子串长度
    {
        for(int from=0; from+i<=len; from++)
        {
            MakeChild(from, i);//生成子串
            bool repeat=false;//用来检查这个字串以前是否出现过。先假设没出现过
            for(int i=0; i<n; i++)
            {
                if(strcmp(buf[i].s, child)==0)
                {//如果这个字串以前就出现过，那就直接计数器+1
                    buf[i].count++;
                    repeat=true;
                    break;
                }
            }
            if(!repeat)
            {//这个字串之前没出现过，那就把这个字串加入字串列表，计数器为1
                buf[n].count=1;
                strcpy(buf[n++].s, child);
            }
        }
    }
}

int main()
{
    while(gets(str))
    {
        n=0;//子串列表清零
        LetsGo();//生成子串列表并完成统计
        sort(buf, buf+n, cmp);//给子串列表排序
        for(int i=0; i<n; i++)
        {
            if(buf[i].count>1)//如果出现过不止一次，那就输出
            {
                printf("%s %d\n", buf[i].s, buf[i].count);
            }
        }
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;

int main()
{
    //freopen("data.txt", "r", stdin);
    char str[101];
    string s;
    map<string, int> Map;
    while(scanf("%s", str) != EOF){
        s.assign(str);
        for(int i = 0; i < strlen(str); i++)
            for(int j = 1; j <= strlen(str) - i; j++)
                Map[s.substr(i, j)]++;

        map<string, int>::iterator it;
        for(it = Map.begin(); it != Map.end(); it++)
            if(it->second > 1)
                printf("%s %d\n", it->first.c_str(), it->second);
    }
    return 0;
}

我爱STL

#include<iostream>
#include<map>
#include<string>
using namespace std;

map<string, int> mp;

int main(){
    string str;
    while(cin >> str){
        for(int i = 0; i <= str.length(); i++){
            for(int j = 0; j < i; j++){
                string sub_str = str.substr(j, i - j);
                mp[sub_str]++;
            }
        }

        for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++){
            if(it -> second > 1)
                cout << it -> first << ' ' << it -> second << endl;
        }
    }
    return 0;
}

#既然全部循环查找所有的子串，就不使用字符串的count()方法了
while True:
    try:
        string = input()
        stringLen = len(string)
        result = {}
        for i in range(stringLen):
            for j in range(i+1,stringLen+1):
                tempSub = string[i:j]
                if tempSub not in result:
                    result[tempSub] = 1
                else:
                    result[tempSub] += 1
        result = list(filter(lambda x:x[1] != 1,result.items()))
        result.sort(key=lambda x:x[0])
        for i in result:
            print("%s %d"%(i[0],i[1]))
    except Exception:
        break

#include<iostream>
#include<string>
#include<map>
using namespace std;

// 利用map可以自动字典排序并且计数
 void find_multiple_zichuan(string &str)
 {
     //步长，从0步开始代表自身
	 int len=0;
	 string s;
	 map<string ,int> m_a;
     //每次提取子串 更新map中的计数
	 for(int i=0;i<str.size();i++)
	 {
		 for(int j=0;j+len<str.size();j++)
		 {
			 s=str.substr(j,len+1);
			 m_a[s]++;
		 }
         len++;
	 }
     //最后统计大于1的串即为结果
	 for(auto i=m_a.begin();i!=m_a.end();i++)
	 {
		 if(i->second>1) cout<<i->first<<" "<<i->second<<endl;
	 }

 }
int main()，
{
	string str;
	while(cin>>str)
	{
		find_multiple_zichuan(str);
	}

}

#include <iostream>
using namespace std;
#include<map>
int main() {
    string str;
    cin >> str;
    int flag = 0;
    map<string, int> m;
    for (int i = 0; i < str.length(); i++) {
        for (int j = i + 1; j <= str.length(); j++){
            flag=0;
            for (map<string, int>::iterator it = m.begin(); it != m.end(); it++) {
                if (it->first == str.substr(i, j-i)) {
                    it->second++;
                    flag = 1;
                    break;
                }
            }if(flag==0){
                m.insert(make_pair(str.substr(i,j-i), 1));
            }
        }
    }for(map<string,int>::iterator it=m.begin();it!=m.end();it++){
        if(it->second>1){
            cout<<it->first<<" "<<it->second<<endl;
        }
    }
}

#include <cstdio>
#include <iostream>
#include <map>

using namespace std;

// 子串计算 ——字典中不会有重复的元素！ 
int main() {
	string str;
	while (getline(cin, str)) {
		map<string, int> number;
		
		for (int i = 0; i <= str.size(); i++) {
			for (int j = 0; j < i; j++) {
				string s = str.substr(j, i-j); // 每一个字符串
				number[s]++;// 计算出现次数 
			}
		}
		
		map<string, int>::iterator it;// 迭代器 
		for (it = number.begin(); it != number.end(); it++) {
			if (it->second > 1) {// 大于1输出 
				cout << it->first << " " << it->second << endl;
			}
		}
	}
	return 0;
} 
//10101

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    string s;
    map<string,int> strmap;
    map<string,int>::iterator it;
    cin >> s;
    int n=s.length();
    for(int i=0;i<n;i++){//二重循环，找出所有子串，加入字典
        for(int j=1;j<=n-i;j++){
            string babystr=s.substr(i,j);//拿到子串
            it=strmap.find(babystr);//找字典里有没有该子串
            if(it!=strmap.end()){
                it->second++;//有该子串，值+1
            }else{
                strmap[babystr]=1;//没有该字串，添加进字典
            }
        }
    }
    for(it=strmap.begin();it!=strmap.end();it++){
        if(it->second>1){//要求输出数量>1的子串
            cout << it->first << " " << it->second << endl;
        }
    }
}