Cod sursa(job #1508917)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 23 octombrie 2015 09:48:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000010],B[2000010];
int urm[2000010];
vector<int> h;
void urmat(int n)
{
    int k=-1,x;
    urm[0]=0;
    for(x=1;x<n;x++)
    {
        while(k>0 && A[k+1]!=A[x]) k=urm[k];
        if(A[k+1]==A[x]) k++;
        urm[x]=k;
    }
}
int main()
{
    fin>>A>>B;
    int n=strlen(A),m=strlen(B),i,k=-1;
    urmat(n);
    for(i=0;i<m;i++)
    {
        while(k>0&& A[k+1]!=B[i]) k=urm[k];
        if(A[k+1]==B[i]) k++;
        if(k==n-1)
        {
            h.push_back(i-n+1);
        }
    }
    fout<<h.size()<<"\n";
    i=1;
    for(vector<int>::iterator it=h.begin();it!=h.end();it++)
    {
        fout<<*it<<" ";
        if(i==999) break;
        else i++;
    }
}