Cod sursa(job #2074782)

Utilizator doruliqueDoru MODRISAN dorulique Data 24 noiembrie 2017 23:48:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

char s[2000010],p[2000010];
int l[2000010],sl[2000010];

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin.getline(p,2000010);
    fin.getline(s,2000010);
    int n=strlen(s),m=strlen(p),i=1,j=0,ns=0;
    l[0]=0;
    while(i<m)
        if(p[i]==p[j])
        {
            l[i]=j+1;i++;j++;
        }
        else if(j==0){l[i]=0;i++;}
             else j=l[j-1];
    i=j=0;
    while(i<n)
        if(s[i]==p[j])
        {
            i++;j++;
            if(j==m)
            {
                sl[ns++]=i-m;
                j=l[j-1];
            }
        }
        else if(j==0)i++;
            else j=l[j-1];
    fout<<ns<<"\n";
    if(ns>1000)ns=1000;
    for(i=0;i<ns;i++)fout<<sl[i]<<" ";
    return 0;
}