Cod sursa(job #1463901)

Utilizator doruliqueDoru MODRISAN dorulique Data 21 iulie 2015 19:43:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

char p[2000010],s[2000010];
int q[2000010],poz[1010];

int main()
{
    fstream f("strmatch.in",ios::in);
    f.getline(p,2000010);
    f.getline(s,2000010);
    f.close();
    f.open("strmatch.out",ios::out);
    int i=1,j=0,lp=strlen(p),ls=strlen(s);
    q[0]=0;
    while(i<lp)
        if(p[i]==p[j])
            q[i++]=++j;
        else if(j)
            j=q[j-1];
        else
            q[i++]=0;
    int n=0;
    i=0;
    j=0;
    while(i<ls)
        if(s[i]==p[j])
        {
            i++,j++;
            if(j==lp)
            {
                n++;
                if(n<=1000)
                    poz[n]=i-j;
            }
        }
        else if(j)
            j=q[j-1];
        else
            i++;
    f<<n<<"\n";
    for(i=1; i<=min(n,1000); i++)f<<poz[i]<<" ";
    return 0;
}