Substring Characters

The set of distinct characters in a string is referred to as the generalized period of the string. As an example, the generalized period of the string “aabbabb” is {‘a’,‘b’}

A proper substring is a contiguous substring that is contained in a string and is not the string itself. So “aabbabb” is not a proper substring of the above example.

A minimal proper substring is one that can have no character removed from either end and still have the same generalized period. “aabb” is a proper substring of the example, but it is not minimal. “ab” is minimal.

Unique means that multiple occurrences of the same minimal proper substring in a string are only to be counted once. In the example, “ab” appears twice, but is counted once—hence the number of proper minimal unique substrings with the same generalized period of the entire string is two: “ab” and “ba”.

Your team is to write a program to count the number of proper minimal unique substrings of a given string that have the same generalized period as the string itself.

Input to your program is a series of lines terminated by end-of-file. Each line is a test case consisting of alphanumericcharacters (a–z, A–Z, 0–9). Upper-case and lower-case letters are distinct. The new line character is not part of thetest case string. No test case string will exceed $80$ characters. There will be at most $100$ test strings in input.

#include<bits/stdc++.h> using namespace std; #define LL long long int main(){ string s; while(cin>>s){ set<string>q;q.clear(); set<char>p;p.clear(); map<char,int>o;o.clear(); for(int i=0;i<s.size();i++){ p.insert(s[i]); o[s[i]]++; } if(o[s[0]]==1&&o[s[s.size()-1]]==1){ cout<<0<<endl; continue; } int nm=p.size(),flag=0,res=-1,k=0; for(int i=0;i<s.size();i++){ set<char>v;v.clear(); map<char,int>oo;oo.clear(); string c=""; for(int j=i;j<s.size();j++){ c+=s[j]; oo[s[j]]++; v.insert(s[j]); if(v.size()==nm&&oo[s[i]]==1&&oo[s[j]]==1){ q.insert(c); break; } } } cout<<q.size()<<endl; } }

详情