Cod sursa(job #1638558)

Utilizator arhivamanArhiva Man arhivaman Data 8 martie 2016 00:08:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <string.h>
#include <vector>
#define nMax 2000005
#define pb push_back
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int p[nMax], k, n, m, nrSol;
char A[nMax], B[nMax];
vector<int> Sol;
void read()
{
    fin>>A+1>>B+1;
    n=strlen(A+1), m=strlen(B+1);
}
void prefix()
{
    for(int i=2;i<=n;i++)
    {
        while(k && A[k+1]!=A[i])
            k=p[k];
        if(A[k+1]==A[i])
            k++;
        p[i]=k;
    }
}
void solve()
{
    prefix();
    k=0;
    for(int i=1;i<=m;i++)
    {
        while(k && A[k+1]!=B[i])
            k=p[k];
        if(A[k+1]==B[i])
            k++;
        if(k==n)
        {
            if(Sol.size()<1000)
                Sol.pb(i-n);
            nrSol++;
            k=p[k];
        }
    }
}
void write()
{
    fout<<nrSol<<'\n';
    for(vector<int>::iterator it=Sol.begin();it!=Sol.end();it++)
        fout<<*it<<" ";
}
int main()
{
    read();
    solve();
    write();
    return 0;
}