?
Nun habe ich mein Programm endlich fertig Verbessrungsvorschläge zur Optimierung etc. sind natürlich gerne gesehen!
/*
============================================================================
Name : Periods / main.cpp
Author : Christian Ivicevic
Description : 42
============================================================================
*/
/*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the
* Free Software Foundation; either version 2, or (at your option) any
* later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
*/
#include <iostream> // I/O
#include <string> // std::string
#include <vector> // matrix in levenshtein and input
namespace periods {
// Returns the exact period of a given string if there is one; otherwise the
// given string.
std::string getExactPeriod(std::string const& x);
// Returns the edit distance between two given objets s1 and s2 over
// an alphabet Sigma.
template <class _Ty>
unsigned int levenshtein(const _Ty& s1, const _Ty& s2);
}
// Main function.
int main(int argv, char **argc) {
// vector holding all input strings.
std::vector<std::string> vx, vy;
// pointers to strings
std::string *x, *y;
// the minimum integer value k such that a string y is a k-approximate period
// of string x.
unsigned int k = INT_MAX - 1;
/* INPUT */
unsigned int iTestCases = -1;
std::cin >> iTestCases;
for(unsigned int temp = 0; temp < iTestCases; ++temp) {
std::string string;
// read string y
std::cin >> string;
vy.push_back(string);
// read string x
std::cin >> string;
vx.push_back(string);
}
std::cout << "--------------------------" << std::endl;
/* LOOP */
for(unsigned int iCurrentCase = 0; iCurrentCase < iTestCases; ++iCurrentCase) {
x = &vx[iCurrentCase];
y = &vy[iCurrentCase];
std::string::size_type length = x->length();
// check whether we have an exact period
// both sides can be periodic and a period of themselves!
if(periods::getExactPeriod(y[0]) == periods::getExactPeriod(x[0]))
k = 0;
// approximate period
if(k != 0) {
// iteration
for(unsigned int i = 0; i <= length; ++i) {
for(unsigned int j = i; j < length; ++j) {
if(j != 0) {
// look for minimal distance
unsigned int dist = periods::levenshtein(*y, x->substr(i, j));
if(dist != 0 && dist < k)
k = dist;
}
}
}
}
std::cout << k << std::endl;
// reset for next test case
k = INT_MAX - 1;
}
/* END */
std::cin.get();
std::cin.get();
return 0;
}
namespace periods {
// Returns the exact period of a given string if there is one; otherwise the
// given string.
std::string getExactPeriod(std::string const& x) {
std::string::size_type length = x.length();
// start at the end to check high powers first
for(unsigned int k = length; k > 1; --k) {
// not splittable in k substrings
if(length % k) continue;
// divide string in k parts of length dist
std::size_t dist = length / k;
// first
char const* first = x.data();
// last
char const* last = first + ((k - 1) * dist);
// iterate over every substring except the last one!
for(; first < last; first += dist) {
// compare with successor: break if not equal
if(strncmp(first, first+dist, dist)) break;
}
// if the loop is at the end all substrings were equal
if(first==last)
return std::string(first, first+dist);
}
return x;
}
// Returns the edit distance between two given objets s1 and s2 over
// an alphabet Sigma.
template <class _Ty>
unsigned int levenshtein(const _Ty& s1, const _Ty& s2) {
// create matrix
const std::size_t len1 = s1.size(), len2 = s2.size();
std::vector< std::vector<unsigned int> > d(len1 + 1, std::vector<unsigned int>(len2 + 1));
// recurrencies
d[0][0] = 0;
for(unsigned int i = 1; i <= len1; ++i) d[i][0] = i;
for(unsigned int i = 1; i <= len2; ++i) d[0][i] = i;
for(unsigned int i = 1; i <= len1; ++i)
for(unsigned int j = 1; j <= len2; ++j)
d[i][j] = std::min(std::min(d[i - 1][j] + 1,d[i][j - 1] + 1), d[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1));
// the result is the last pivot!
return d[len1][len2];
}
}
/* EOF */
