Cod sursa(job #1989095)

Utilizator b10nd3Oana Mancu b10nd3 Data 5 iunie 2017 19:54:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<string>

using namespace std;

int main(){
ifstream in; ofstream out;
in.open("strmatch.in"); out.open("strmatch.out");
out.clear();

string a,b;
int i,q,howMany=0,lengthA,lengthB;

in>>a>>b;
lengthA=a.length(); lengthB=b.length();
int match[1001],pi[lengthA];

//prefix for a
q=-1; pi[0]=-1;
for(i=1;i<lengthA;i++){
while(q>-1 && a[i]!=a[q+1]) q=pi[q];
if(a[q+1]==a[i]) q++;
pi[i]=q;
}

q=-1;
for(i=0;i<lengthB;i++){
   while(q>-1 && a[q+1]!=b[i]) q=pi[q];
   if(a[q+1]==b[i]) q++;
   if(q==lengthA-1) {howMany++; if(howMany<=1000) match[howMany]=i-lengthA+1;}
}

out<<howMany<<endl;
if(howMany>1000) howMany=1000;
for(i=1;i<=howMany;i++) out<<match[i]<<" ";

return 0;
}