Cod sursa(job #2067677)

Utilizator valentinoltyanOltyan Valentin valentinoltyan Data 16 noiembrie 2017 19:00:01
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

char a[2000001],b[2000001];
int v[2000001],r[2000001];
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a>>b;
    int n=strlen(a);
    int m=strlen(b);
    int p=0;
    int i=0,j=-1;
    v[i]=0;
    while(i<n)
    {
        while(j>0&&a[i]!=a[j])
            j=v[j];
        i++;j++;
        v[i]=j;
    }
    j=0;i=0;
   // for(int i=0;i<n;i++)
   //     cout<<v[i]<<" ";
    while (i<m)
    {
        while (j>0&&b[i]!=a[j])
            j=v[j];
        i++;
        j++;
        if (j==n&&p<1000)
        {
            r[p]=i-n;
            p++;
            j=v[j];
        }
    }
    g<<p<<endl;
    for(i=0;i<p;i++)
        g<<r[i]<<" ";
    return 0;
}