Cod sursa(job #1138706)

Utilizator UAIC_Balan_Negrus_HreapcaUAIC Balan Negrus Hreapca UAIC_Balan_Negrus_Hreapca Data 10 martie 2014 14:47:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 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 <random>
#include <assert.h>
using namespace std;

const string file = "strmatch";

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

const int INF = 0x3f3f3f3f; 

//#define ONLINE_JUDGE

vector<int> computeFail(string& A)
{
    int N = A.length();
    vector<int> fail(N);
    int c = 0;
    for(int i = 1; i < N; i++)
    {
        while(c != 0 && A[i] != A[c])
        {
            c = fail[c - 1];
        }
        if(A[i] == A[c])
        {
            c++;
        }
        fail[i] = c;
    }
    return fail;
}

int main()
{
#ifdef ONLINE_JUDGE
	ostream &fout = cout;
	istream &fin = cin;
#else
	fstream fin(infile.c_str(), ios::in);
	fstream fout(outfile.c_str(), ios::out);
#endif	

    string A, B;
    fin >> A >> B;
    vector<int> fail = computeFail(A);
    int N = A.length();
    int M = B.length();

    vector<int> Sol;
    int mCount = 0;
    int c = 0;

    for(int i = 0; i < M; i++)
    {
        while(c != 0 && A[c] != B[i])
        {
            c = fail[c - 1];
        }
        if(A[c] == B[i])
        {
            c++;
        }
        if(c == N)
        {
            mCount++;
            if(mCount <= 1000)
            {
                Sol.push_back(i - N + 1);
            }
        }
        
    }
    fout << mCount << "\n";
    for(vector<int>::iterator itr = Sol.begin();
            itr != Sol.end();
            itr++)
    {
        fout << *itr << " ";
    }
    fout << "\n";
#ifdef ONLINE_JUDGE
#else
    fout.close();
	fin.close();
#endif
}