Cod sursa(job #1074954)

Utilizator hainagiudanielHainagiu Daniel hainagiudaniel Data 8 ianuarie 2014 11:01:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define nmax 2000005
string s1,s2;
int p[nmax];
int n,m;

void prefix()
{
    int k;
    k=0;
    p[1]=0;
    for(int i=2;i<=n;i++)
    {
        while(k && s1[k+1]!=s1[i])
            k=p[k];
        if(s1[k+1]==s1[i])
            k++;

        p[i]=k;

    }
}

int main()
{
    int k=0;
    vector <int>  r;
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    getline(in,s1);
    s1="*"+s1;
    getline(in,s2);
    s2="%"+s2;
    n=s1.size()-1;
    m=s2.size()-1;
    prefix();
    for(int i=1;i<=m;i++)
    {
        while(k && s1[k+1]!=s2[i])
            k=p[k];
        if(s1[k+1]==s2[i])
                    k++;
        if(k==n)
           {

            r.push_back(i-n);
            k=p[k];
        }
    }
    k=r.size();
    out<<k<<"\n";
    for(unsigned int i=0;i<min(k,1000);i++)
        out<<r[i]<<" ";
    return 0;
}