Pagini recente » Cod sursa (job #878912) | Cod sursa (job #2805949) | Cod sursa (job #3135967) | Cod sursa (job #1824632) | Cod sursa (job #2977749)
/// strmatch de pe infoarena cu KMP
#include <fstream>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char v[4000001];
int pi[2000001];
int main()
{
int n=0,i,l,nrap=0;
char ch;
cin.get(ch);
while(ch!='\n')
{
v[++n]=ch;
cin.get(ch);
}
pi[1]=0;
l=n;
i=1;
n++;
v[n]='#';
n++;
cin.get(v[n+1]);
n++;
while(cin.get(v[n]))
{
i++;
pi[i]=pi[i-1];
while(pi[i]!=0 && v[pi[i]+1]!=v[n])
{
pi[i]=pi[pi[i]];
}
if(v[pi[i]+1]==v[n])
pi[i]++;
if(pi[i]==l)
nrap++;
n++;
}
n--;
cout<<nrap;
return 0;
}