Cod sursa(job #1016013)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 25 octombrie 2013 16:12:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iterator>
#include <assert.h>
using namespace std;

const string file = "strmatch";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;

string A;
string B;
vector<int> fail;
vector<int> matches;
int Sol;
int N;

void computeFail()
{
	fail.resize(N);

	int c = 0;
	for(unsigned i = 1; i < N; i++)
	{
		while(A[c] != A[i] && c != 0)
		{
			c = fail[c - 1];
		}
		if(A[c] == A[i])
		{
			fail[i] = ++c;
		}
	}

}


void match()
{
	int c = 0;
	for(unsigned i = 0; i < B.length(); i++)
	{
		while(A[c] != B[i] && c != 0)
		{
			c = fail[c - 1];
		}
		if(A[c] == B[i])
		{
			c++;
		}

		if(c == N)
		{
			Sol++;

			if(Sol <= 1000)
			{
				matches.push_back(i - N + 1);
			}

			c = fail[c - 1];
		}
	}
}

int main()
{
	fstream fin(infile.c_str(), ios::in);
	fin >> A;
	fin >> B;
	N = A.length();
	fin.close();

	computeFail();
	match();
	fstream fout(outfile.c_str(), ios::out);
	fout << Sol << "\n";
	for(vector<int>::iterator itr = matches.begin();
		itr != matches.end();
		itr++)
	{
		fout << *itr << " ";
	}
	fout << "\n";
	fout.close();
}