Cod sursa(job #2084345)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 8 decembrie 2017 23:08:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

char pattern[2000010], str[2000010];
int l[2000010], v[1005];


int main()
{
    int n, m, i, j, x=0, nr=0;
    ifstream fin ("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> pattern >> str;
    n=strlen(str);
    m=strlen(pattern);
    i=1;
    j=0;
    l[0]=0;
    while(i<m)
        if(pattern[i]==pattern[j])
        {
            l[i]=j+1;
            i++,j++;
        }
        else if(j==0) l[i++]=0;
        else j=l[j-1];
    i=j=0;
    while(i<n)
        if(str[i]==pattern[j])
        {
            i++,j++;
            if(j==m)
            {
                nr++;
                if (nr<=1000)
                    v[x++]=i-m;
                j=l[j-1];
            }
        }
        else if(j==0)i++;
        else j=l[j-1];
    fout << x << "\n";
    for (i=0; i<x; i++)
        fout << v[i] << " ";
    return 0;
}