Cod sursa(job #1735440)

Utilizator DorelBarbuBarbu Dorel DorelBarbu Data 29 iulie 2016 21:00:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int MAXN = 2000000;

string A, B;

int table[MAXN+1], nA, nB, solSize;
vector <int> sol;

void buildTable()
{
    for(int i = 1; i < nA; i++)
    {
        int left = 0, right = i, m = 0;
        for(int j = i; j >= 1; j--)
           if(A.substr(0,j) == A.substr(i-j+1,j))
            {
                table[i] = j;
                break;
            }
    }

    /*for(int i = 0; i < nA; i++)
        cout<<table[i]<<' ';
    cout<<endl;*/
}

void match(string A, string B)
{
    if(nA > nB)
    {
        cout<<0;
        return;
    }

    int i = 0;

    while(i < nB && nA <= nB - i)
    {
        int j = 0;
        while(B[i+j] == A[j] && j < nA)
        {
            //cout<<i<<' '<<j<<' '<<B[i+j]<<' '<<A[j]<<endl;
            j++;
        }
        if(j == nA)
        {
            //cout<<i<<endl;
            sol.push_back(i);
        }
        if(table[j-1] != 0)
            i=i+j-table[j-1];
        else
            i++;
    }
}


int main()
{
    in>>A>>B;
    nA = A.length();
    nB = B.length();
    buildTable();
    match(A,B);

    if(sol.size() > 1000)
        solSize = 1000;
    else
        solSize = sol.size();

    out<<solSize<<endl;
    for(int i = 0; i < solSize; i++)
        out<<sol[i]<<' ';

    return 0;
}