Cod sursa(job #1508909)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 23 octombrie 2015 09:38:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000001],B[2000001];
int urm[2000001];
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";
    for(vector<int>::iterator it=h.begin();it!=h.end();it++) fout<<*it<<" ";
}