Cod sursa(job #1139691)

Utilizator andreiiiiPopa Andrei andreiiii Data 11 martie 2014 13:20:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
//Z-Algorithm

#include <fstream>
#include <vector>
#include <string>

using namespace std;

const int N=2000005;

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

string a, b, c;
int Z[2*N];

int main()
{
    int i, R, L, k, solnr=0;
    vector <int> sol;
    fin>>a>>b;
    c=a+b;
    R=L=0;
    for(i=1;i<c.size();i++)
    {
        if(i>R)
        {
            L=R=i;
            while(R<c.size()&&c[R]==c[R-L]) R++;
            Z[i]=R-L;
            R--;
        }
        else
        {
            k=i-L;
            if(Z[k]<R-i+1) Z[i]=Z[k];
            else
            {
                L=i;
                while(R<c.size()&&c[R]==c[R-L]) R++;
                Z[i]=R-L;
                R--;
            }
        }
        if(i>=a.size()&&Z[i]>=a.size())
        {
            solnr++;
            if(sol.size()<1000) sol.push_back(i-a.size());
        }
    }
    fout<<solnr<<"\n";
    for(i=0;i<sol.size();i++) fout<<sol[i]<<" ";
    fin.close();
    fout.close();
}