Cod sursa(job #219022)

Utilizator dragosmihaiDragos Oana dragosmihai Data 4 noiembrie 2008 19:58:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

string s1,s2;
vector<int> v;
int pre[2000002];

void prefix(string s)
{
    int l=s.length();
    int k=0;
    for(int i=2;i<l;i++)
    {
        while(k&&s[k+1]!=s[i])
            k=pre[k];
        if(s[k+1]==s[i])
            k++;
        pre[i]=k;
    }
}

void kmp(string s1, string s2)
{
    int l2=s2.length();
    int l1=s1.length()-1;
    int k=0;
    for(int i=1;i<l2;i++)
    {
        while(k&&s1[k+1]!=s2[i])
            k=pre[k];
        if(s1[k+1]==s2[i])
            k++;
        if(k==l1&&v.size()<=1000)
            v.push_back(i-l1);
    }
}

void citire()
{
    ifstream f("strmatch.in");
    f>>s1>>s2;
    f.close();
    s1=" "+s1;
    s2=" "+s2;
    prefix(s1);
}

void scriere()
{
    int l=v.size();
    ofstream g("strmatch.out");
    g<<l<<endl;
    for(int i=0;i<l;i++)
        g<<v[i]<<" ";
}

int main()
{
    citire();
    kmp(s1,s2);
    scriere();
    return 0;
}