Cod sursa(job #1074937)

Utilizator hainagiudanielHainagiu Daniel hainagiudaniel Data 8 ianuarie 2014 10:37:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;

string s1,s2;
vector<int> p;
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;
    p.reserve(n);
    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];
        }
        if(r.size()==1000)
            break;
    }
    out<<r.size()<<"\n";
    for(unsigned int i=0;i<r.size();i++)
        out<<r[i]<<" ";
    return 0;
}