Periods of Strings

[Gast]

Hallo miteinander,

ich habe als Aufgabe in unserem Proseminar eine der Problemstellungen des ACM ICPC zu lösen, jedoch habe ich einige Denkblockaden im Moment.

Zunächst hier die Aufgabenstellung.

Den Anfang mit der Distanz zweier Strings werde ich mit der Levenshtein-Distanz machen - das ist kein Problem. Aber ich scheitere am zweiten Teil den String x in nichtleere Teilstrings aufzuteilen und alle Kombinationen dann durchzugehen und darauf die Levenshtein-Distanz zu bestimmen! Hat einer einen Tipp, wie ich das Teilproblem angehen könnte?

Wäre mir eine große Hilfe, wenigstens ansatzweise einen Tipp zu bekommen

Danke im Voraus

[pumuckl]

Ich würds so angehen:

1. Du zerlegst den String der Länge N in k substrings, wobei k von 1 bis N läuft (okay, die Randwerte 1 und N sind trivial und können evtl. rausgenommen werden...)
   -> mach eine Schleife für k=1..N

2. Bei einer Zerlegung in n Substrings kann der erste substring eine Länge s1 von 1 bis N-(n-1) haben, (im letzten Fall hast du dann s1 = N-(n-1), s2=s3=...=sk=1)
   -> Mach eine Schleife für s1=1..(N-(n-1)) darin entnimmst du den ersten substring und unterteilst rekurdiv den Rest des Strings in n-1 substrings
   -> wenn n=1 ist das zerlegen fertig und du kannst deine substring-sammlung analysieren.

Pseudocode:

string S
substringarray sa
for k:=1..length(S)
  zerlege(S in k)

zerlege(str in n):
  if n = 1
    teste(sa)
    fertig
  else for s1:=1..(length(str) - (n - 1))
    sa.push_back (substring(0..s1 of str))
    zerlege((substring((s1+1)..length(str) of str) in (n-1))

[Gast]

Da ich noch nie sowas verschachteltes gemacht habe, bräcuhte ich vllt. etwas mehr Unterstüzung. Kannst du mir sagen, ob diese Umsetzung dem Pseudocode gerecht wird oder ob ich Blödsinn mit den Pointern anstelle

EDIT:

Code entfernt! Ich habe doch folgende Situation, oder:

(Da hier kein LaTeX angezeigt wird ein kleiner Link)

Dabei ist "klein Sigma" die Substring-Funktion und das frakturierte L der Levenshtein-Algo, der die Strings y und den Teilstring akzeptiert.

[pumuckl]

Christian Ivicevic schrieb:

EDIT:

Code entfernt!

Ich hatte leider grade Meeting, sonst hätte ich dir ein bisshcen Feedback zu dem Code gegeben...

Ich habe doch folgende Situation, oder:

(Da hier kein LaTeX angezeigt wird ein kleiner Link)

Dabei ist "klein Sigma" die Substring-Funktion und das frakturierte L der Levenshtein-Algo, der die Strings y und den Teilstring akzeptiert.

Ähm. Wie genau liefert σ aus zwei Indizes den Substring?
Ist für deine Berechnung die komplette Stringzerlegung wichtig oder nur jeweils ein einzelner Substring?

D.h., beim String "abcd", ist es da wichtig, ob der String in a|b|cd zerlegt wurde oder in ab|cd, wenn du den substring cd betrachtest?
Levenshtein sagt mir grade garnichts, deshalb kann ich dir dazu nicht viel sagen.

[Gast]

Levenshtein ist eh für den Sachverhalt unwichtig. Das ist nur der Algorithmus, den ich auf den String y und die Teilstrings von x anwenden muss. Dieser Teil funktioniert bei mir bisher prima
Allerdings habe ich noch ein Teilproblem zu lösen - wenn dies gelöst ist, kann ich ja mal meinen fertigen Code posten, weil ich bisher das etwas "dirty" habe und noch ein kleiner Bug drin ist.

Angenommen ich habe meinen String x = abababab (Beispiel von der Angabe!), dann entspricht das x = (abababab)^1 = (abab)^2 = (ab)^4. Eine einfache Rekursionsvorschrift der Form s^0 := "", s^n+1 = s*s^n, wobei * für die Konkatenation steht. Wie könnte ich am galantesten diese "exact period", wie sie genannt wird, überprüfen?

// EDIT: allein schon mit der doppelten Summe schaffe ich es alle Substrings zu extrahieren.

[pumuckl]

Christian Ivicevic schrieb:

Wie könnte ich am galantesten diese "exact period", wie sie genannt wird, überprüfen?

wenn exact period heißt, dass es s und i geben muss mit x=sⁱ, dann ist das Problem noch deutlich einfacher:

Sei n die Länge von x.
Für jeden echten Teiler t von n überprüfe:
Bilde t/n Substrings s(0,t-1), ..., s(n-t,n-1) der Länge t und vergleiche sie miteinander. Wenn alle gleich sind, ist x = s(0,t-1)^t

[Gast]

int n = x.length();
bool isExact = false;
for(int t = 2; t < n; t++) {
	if(n % t == 0) {
		string s = x.substr(0, n/t);
		for(int j = n/t; j < n - n/t; j += n/t) {
			if(s != x.substr(j, n/t)) {
				isExact = false;
				break;
			} else
				isExact = true;
		}
	}
}

if(isExact) /* do something ^^ */;

Ich muss zugeben etwas unschön Aber trifft es so in etwa den Gedankengang?

[pumuckl]

Christian Ivicevic schrieb:

Ich muss zugeben etwas unschön

Sehr tiefe Schachtelung, allerdings

Christian Ivicevic schrieb:

Aber trifft es so in etwa den Gedankengang?

Jap.

string exactPeriod(string const& x)
{
  string::size_t length = x.length();
  for (unsigned k = length; k > 1; --i ) //oben anfangen, da die hohen "potenzen" so zuerst geprueft werden
  {
    if (length % k) continue; //nicht in k substrings teilbar

    //wir teilen den string in k substrings der laenge dist
    std::size_t dist = length/k;
    //der erste: 
    char const* first = x.data();
    //letzte davon beginnt (k-1)*dist nach dem ersten
    char const* last = first + ((k-1)*dist);

    //durch alle bis auf den letzten substring iterieren...
    for(; first < last; first += dist)
    { 
      //... und jeden mit seinem Nachfolger vergleichen:
      //bei Ungleichheit Abbruch der Schleife
      if (strncmp(first, first+dist, dist) != 0) break;
    }
    //falls die Schleife komplett durchlaufen wurde waren alle substrings gleich
    if (first==last) return string(first, first+dist);
  }
  return x; //x = x^1
}

//...
string period = period(x);
unsigned exponent = x.length()/perod.length();

[Gast]

Dein string::size_t müsste string::size_type heißen! Zumindest kennt VS bei mir nur das Des Weiteren würde es mich interessieren, ob die string-Klasse nicht Methoden bietet, um nicht auf die Pointer-Ebene gehen zu müssen und Funktionen wie strncmp zu umgehen.

Außerdem muss ich nur prüfen, ob die exakte Periode gleich dem zweiten String ist -> keine Spielerei mit Exponenten etc.

[CStoll]

Christian Ivicevic schrieb:

Dein string::size_t müsste string::size_type heißen! Zumindest kennt VS bei mir nur das Des Weiteren würde es mich interessieren, ob die string-Klasse nicht Methoden bietet, um nicht auf die Pointer-Ebene gehen zu müssen und Funktionen wie strncmp zu umgehen.

Ja, die Klasse bietet so einiges, z.B. überladene Vergleichs-Operatoren oder auch compare().

[Gast]

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 */