Cod sursa(job #2173779)
Utilizator | Data | 16 martie 2018 00:51:29 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.71 kb |
#include <fstream>
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern;
string text;
int nrmatch=0;
vector <int> res;
int pref[2000002];
void gen_pref(string s)
{
int j=0;
for(int i=1; i<s.size(); i++)
{
if(s[i]==s[j])
{
pref[i]=j+1;
j++;
}
else
{
while(j>0)
{
j=pref[j-1];
if(s[j]==s[i])
{
pref[i]=j+1;
j++;
break;
}
}
if(j==0)
{
if(s[j]!=s[i])
pref[i]=0;
else
{
pref[i]=j+1;
j++;
}
}
}
}
}
void solve(string t, string p)
{
int j=0;
for(int i=0; i<t.size(); i++)
{
if(t[i]==p[j])
{
if(j==p.size()-1)
{
nrmatch++;
if(nrmatch<=1000)
{
res.push_back(i-p.size()+1);
}
j=pref[j];
}
else
j++;
}
else if(j!=0)
{
j=pref[j-1];
i--;
}
}
}
int main()
{
getline(fin, pattern);
getline(fin, text);
gen_pref(pattern);
solve(text, pattern);
fout << nrmatch << '\n';
for(int i=0; i<res.size(); i++)
fout << res[i] << " ";
return 0;
}