| 123456 |
- #include <cstdint>
- #include <iostream>
- #include <unordered_map>
- #include <vector>
- using namespace std;
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;string s;cin>>n>>s;vector<int>parent(1);vector<char>top(1);vector<long long>frequency(1,1);unordered_map<uint64_t,int>id;id.reserve(n*2);int state=0;long long answer=0;for(unsigned char c:s){if(state&&top[state]==c)state=parent[state];else{uint64_t key=(uint64_t(state)<<8)|c;auto it=id.find(key);if(it==id.end()){state=parent.size();id[key]=state;parent.push_back((int)(key>>8));top.push_back(c);frequency.push_back(0);}else state=it->second;}answer+=frequency[state]++;}cout<<answer<<'\n';}
|
