cp-algorithms · RodionGork · Oct 5, 2016 · Oct 4, 2016 · Oct 4, 2016 · Oct 4, 2016
diff --git a/src/graph/finding-negative-cycle-in-graph.md b/src/graph/finding-negative-cycle-in-graph.md
@@ -0,0 +1,78 @@
+#Finding a negative cycle in the graph
+
+A directed weighted graph G with n vertices and m edges. Required to find it in any of the negative cycle of weight, if any.
+
+These two options to solve the problem. It is convenient different algorithms, so both of them will be discussed below.
+
+#The decision by the algorithm of Bellman-Ford
+
+Bellman-Ford algorithm allows you to check the presence or absence of the negative weight cycle in the graph, and if present then find one of these cycles.
+
+We will not go into details (which are described in the article on the algorithm of Bellman-Ford ), and give only the result - how the algorithm works.
+
+done n iterations of the algorithm of Bellman-Ford, and if at the last iteration has been no change - the negative cycle in the graph not present. Otherwise, take the top, the distance to which has changed and will go on from her ancestors until will enter the ring; this cycle will be the desired negative cycle.
+
+#Implementation:
+
+	struct edge {
+		int a, b, cost ;
+	} ;
+
+	int n, m ;
+	vector < edge > e ;
+	const int INF = 1000000000 ;
+
+	void solve ( ) {
+		vector < int > d ( n ) ;
+		vector < int > p ( n, - 1 ) ;
+		int x ;
+		for ( int i = 0 ; i < n ; ++ i ) {
+			x = - 1 ;
+			for ( int j = 0 ; j < m ; ++ j )
+				if ( d [ e [ j ] . b ] > d [ e [ j ] . a ] + e [ j ] . cost ) {
+					d [ e [ j ] . b ] = max ( - INF, d [ e [ j ] . a ] + e [ j ] . cost ) ;
+					p [ e [ j ] . b ] = e [ j ] . a ;
+					x = e [ j ] . b ;
+				}
+		}
+
+		if ( x == - 1 )
+			cout << "No negative cycle found." ;
+		else {
+			int y = x ;
+			for ( int i = 0 ; i < n ; ++ i )
+				y = p [ y ] ;
+
+			vector < int > path ;
+			for ( int cur = y ; ; cur = p [ cur ] ) {
+				path. push_back ( cur ) ;
+				if ( cur == y && path. size ( ) > 1 )  break ;
+			}
+			reverse ( path. begin ( ) , path. end ( ) ) ;
+
+			cout << "Negative cycle: " ;
+			for ( size_t i = 0 ; i < path. size ( ) ; ++ i )
+				cout << path [ i ] << ' ' ;
+		}
+	} 
+
+#The decision by the algorithm of Floyd-Warshall
+
+Floyd-Warshall algorithm allows to solve a second statement of the problem - when you need to find all pairs of vertices (i, j) Between which there is not the shortest path (ie, it has an infinitesimal amount).
+
+Again, a more detailed explanation is contained in the description of the algorithm of Floyd-Warshall , but here we present only the result.
+
+Once the algorithm of Floyd-Warshall will work for the input graph Let's brute force over all pairs of vertices (i, j) And check infinitesimal shortest path for each pair of i at j or not. To do this Let's brute over the third vertex t And if it turned out for her d [t][t] <0 (i.e. it is in a cycle of negative weight), and she is accessible from i and because it is achievable j - The path (i, j) It could have infinitesimal length.
+
+#Implementation:
+
+	for ( int i = 0 ; i < n ; ++ i )
+		for ( int j = 0 ; j < n ; ++ j )
+			for ( int t = 0 ; t < n ; ++ t )
+				if ( d [ i ] [ t ] < INF && d [ t ] [ t ] < 0 && d [ t ] [ j ] < INF )
+					d [ i ] [ j ] = - INF ; 
+
+Tasks in the online judges
+
+The list of tasks that need to search for a cycle of negative weight:
+* [UVA: Wormholes](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499)
diff --git a/src/index.md b/src/index.md
@@ -24,6 +24,7 @@ especially popular in field of competitive programming.*
 ### String Processing
 - [Suffix Array](./string/suffix-array.html)
 - [Z-function](./string/z-function.html)
+- [Rabin-Karp Algorithm](./string/rabin-karp-algorithm.html)
 
 ### Linear Algebra
 - [Gauss & System of linear equation](./linear_algebra/linear-system-gauss.html)
@@ -40,6 +41,7 @@ especially popular in field of competitive programming.*
 - [Kirchhoff theorem](./graph/kirchhoff-theorem.html)
 - [Topological sorting](./graph/topological-sort.html)
 - [Searching for bridges in O(N+M)](./graph/bridge-searching.html)
+- [Finding a negative cycle in the graph](./graph/finding-negative-cycle-in-graph.html)
 
 ---
 

diff --git a/src/string/rabin-karp-algorithm.md b/src/string/rabin-karp-algorithm.md
@@ -0,0 +1,44 @@
+# Rabin-Karp Algorithm search substring in a string of O (N)
+
+This algorithm is based on the lines of hashing, and those who are not familiar with the subject, refer to the [hashing algorithm in problems on the line](http://e-maxx.ru/algo/string_hashes) .
+
+
+
+The authors of the algorithm - Rabin (Rabin) and Carp (Karp), 1987.
+
+Given a string S and a text T, consisting of small Latin letters. We required to find all occurrences of the string S to the T text in time O (| S | + | T |).
+
+Algorithm. Calculate hash string for S. Calculate hash values for all line prefixes T. Now Let's brute over all the length of the substring T length | S | and each comparable to | S | in O (1).
+
+#Implementation
+	string s, t; // input data
+
+	// Assume all powers of p
+	const int p = 31;
+	vector <long long> p_pow (max (s.length (), t.length ()));
+	p_pow [0] = 1;
+	for (size_t i = 1; i <p_pow.size (); ++ i)
+		p_pow [i] = p_pow [i-1] * p;
+
+	// Calculate the hashes of all line prefixes T
+	vector <long long> h (t.length ());
+	for (size_t i = 0; i <t.length (); ++ i)
+	{
+		h [i] = (t [i] - 'a' + 1) * p_pow [i];
+		if (i) h [i] + = h [i-1];
+	}
+
+	// Calculate the hash of the string S
+	long long h_s = 0;
+	for (size_t i = 0; i <s.length (); ++ i)
+		h_s + = (s [i] - 'a' + 1) * p_pow [i];
+
+	// Iterate over all the length of the substring T | S | and compare them
+	for (size_t i = 0; i + s.length () - 1 <t.length (); ++ i)
+	{
+		long long cur_h = h [i + s.length () - 1];
+		if (i) cur_h - = h [i-1];
+		// Give the hashes to the same extent and compare
+		if (cur_h == h_s * p_pow [i])
+			cout << i << '';
+	}