#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; }
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(); } } } }
#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); } }
#!/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> #include<vector> #include<algorithm> using namespace std; string cut_string(string input,int start_index,int end_index){ //返回剪切的字符串,start和end对应的都是下标 string cut=""; for(int i=start_index;i<=end_index;++i) cut+=input[i]; return cut; } vector<string> get_all_substrings(string input){ vector<string> all_substrings; //第一层循环:控制子串长度 for(int sub_len=1;sub_len<input.length();++sub_len){ //第二层循环:获取子串 for(int i=0;i+sub_len<=input.length();++i){ //截获当前子串 string sub=cut_string(input,i,i+sub_len-1); //需要进行去重检查 bool already_exist=false; for(int j=0;j<all_substrings.size();++j){ if(sub==all_substrings[j]) already_exist=true; } //这个子串没有被放进来过才加入 if(already_exist==false) all_substrings.push_back(sub); } } //排序 sort(all_substrings.begin(),all_substrings.end()); return all_substrings; } int main(){ string input; cin>>input; vector<string> result=get_all_substrings(input); //开始统计每个子串出现的次数 vector<int> count; for(int i=0;i<result.size();++i) count.push_back(0); //第一层循环:遍历所有的子串 for(int i=0;i<result.size();++i){ //第二层循环:统计子串出现的次数 for(int j=0;j+result[i].length()<=input.length();++j){ //获取相同长度的子串 string sub=cut_string(input,j,j+result[i].length()-1); //把获取到的子串与当前的比较 if(sub==result[i]) ++count[i]; } } for(int i=0;i<result.size();++i){ //要求输出出现1次以上的(至少两次) if(count[i]<=1) continue; cout<<result[i]<<" "<<count[i]<<endl; } return 0; }
#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; }
import java.util.Map; import java.util.Scanner; import java.util.TreeMap; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.nextLine(); TreeMap<String, Integer> map = new TreeMap<>(); for (int i = 0; i < s.length(); i++) { for (int j = i; j <s.length(); j++) { String s1 = s.substring(i, j+1); map.merge(s1, 1, Integer::sum); } } for (Map.Entry<String, Integer> entry : map.entrySet()) { if (entry.getValue()>1){ System.out.println(entry.getKey()+" "+entry.getValue()); } } } }
#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 <stdio.h> #include <stdlib.h> #include <string.h> typedef struct TreeNode { int count; char val; // 0-左 1-右 struct TreeNode* left; //左节点-0 struct TreeNode* right; //右节点-1 } TNode; void printTree(char* t, TNode* root) { //前序遍历打印二叉树 if (root) { if (root->count > 1) { //输出t中的所有字符,并且打印本次遍历的字符 printf("%s%c %d\n", t, root->val, root->count); } int length = 0; for (int i = 0; t[i] != '\0'; i++) { length++; } t[length] = root->val; printTree(t, root->left); printTree(t, root->right); t[length] = '\0'; //剪枝 } } void getSubParam(char s[]) { //构建一颗二叉树,字典树 TNode* initNode = (TNode*)malloc(sizeof(TNode)); //创世块 int length = 0; while (s[length] != '\0') { length++; } for (int i = 0; i < length; i++) { TNode* tmp = initNode; for (int j = i; j < length; j++) { //双重循环 if (s[j] == '0') { if (!tmp->left) { //没有左孩子,手动申请一个空间放左孩子 tmp->left = (TNode*)malloc(sizeof(TNode)); tmp->left->val = '0'; tmp->left->count = 0; } tmp->left->count++; tmp = tmp->left; } if (s[j] == '1') { if (!tmp->right) { tmp->right = (TNode*)malloc(sizeof(TNode)); tmp->right->val = '1'; tmp->right->count = 0; } tmp->right->count++; tmp = tmp->right; } } } char* tmp1 = (char*)malloc(sizeof(char) * 101); char* tmp2 = (char*)malloc(sizeof(char) * 101); printTree(tmp1, initNode->left); printTree(tmp2, initNode->right); } //字典二叉树 int main() { char s[100]; // FILE* fp = fopen("./data.in", "r"); while (scanf("%s\n", s) != EOF) { getSubParam(s); } }
我爱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 <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<map> #include<string> using namespace std; int main() { string str; map<string,int> m; while(cin>>str){ for(int i=0;i<str.size();i++){ for(int j=0;j<=i;j++){ string key = str.substr(j,i-j+1); m[key]++; } } } map<string,int>::iterator it; for(it = m.begin();it!= m.end(); it++){ if(it->second>1) cout<<it->first<<" "<<it->second<<endl; } return 0; }
#include <iostream> #include <map> #include <string> using namespace std; int main() { string s; map<string,int> q; while(cin>>s) { for(int i=0; i<s.size(); i++) { for(int j=i; j<s.size(); j++) { string a=s.substr(i,j-i+1); q[a]++; } } map<string,int>::iterator it; for(it=q.begin(); it!=q.end(); it++) { if(it->second>1) cout<<it->first<<" "<<it->second<<endl; } q.clear(); } return 0; }