Cod sursa(job #1509080)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 23 octombrie 2015 14:39:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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=0,i;
    for(i=2;i<=n;i++)
    {
        while(k>0 && A[k+1]!=A[i]) k=urm[k];
        if(A[k+1]==A[i]) k++;
        urm[i]=k;
    }
}
int main()
{
    fin>>(A+1)>>(B+1);
    int n=strlen(A+1),m=strlen(B+1),i,k=0;
    urmat(n);
    for(i=1;i<=m;i++)
    {
        while(k>0&& A[k+1]!=B[i]) k=urm[k];
        if(A[k+1]==B[i]) k++;
        if(k==n)
        {
            h.push_back(i-n);
        }
    }
    fout<<h.size()<<"\n";
    i=1;
    for(vector<int>::iterator it=h.begin();it!=h.end();it++)
    {
        fout<<*it<<" ";
        if(i==1000) break;
        i++;
    }
}