Cod sursa(job #2066980)

Utilizator valentinoltyanOltyan Valentin valentinoltyan Data 15 noiembrie 2017 19:05:41
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 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 i=0,j=1,p=0;
    v[0]=0;
    while(j<n)
    {
        if(a[i]==a[j])
        {
            v[j]=v[i]+1;
            i++;j++;
        }
        if(a[i]!=a[j])
        {
            if(i>0)
                i--;
            else
            {
                j++;
                i=0;
            }
        }
    }
    j=0;i=0;
    while(i<m)
    {
        while(b[i]==a[j]&&j<n&&i<m)
        {
            i++;
            j++;
        }
        if(j==n)
        {
            r[p]=i-n;
            p++;
        }
        if(v[j-1]!=0)
        {
            j=v[j-1];
        }
        else
        {
            i++;
            j=0;
        }

    }
    g<<p<<endl;
    for(i=0;i<p;i++)
        g<<r[i]<<" ";
    return 0;
}