Pagini recente » Cod sursa (job #1884760) | Cod sursa (job #1409890) | Cod sursa (job #1588746) | Cod sursa (job #2850918) | Cod sursa (job #1344619)
#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
FILE*f=fopen("strmatch.in","r"),*g=fopen("strmatch.out","w");
int n, m, l, aux[2000005];
char s[2000005], a[2000005];
vector<int> sol;
int main()
{
fscanf(f,"%s\n",s+1);
fscanf(f,"%s\n",a+1);
n = strlen(s+1);
m = strlen(a+1);
l = 0;
for(int i = 2; i <= n; i++ )
{
while(l > 0 && s[i] != s[l+1])
l = aux[l];
if(s[i] == s[l+1])
{
l++;
aux[i] = l;
}
}
int nr = 0;
l = 0;
for(int i = 1; i <= m; i++)
{
while(l > 0 && a[i] != s[l+1])
l = aux[l];
if(a[i] == s[l+1])
{
l++;
}
if(l == n)
{
nr++;
sol.push_back(i-n);
l = aux[l];
}
}
fprintf(g,"%d\n",nr);
for(vector<int>::iterator it = sol.begin(); it != sol.end(); it++)
{
fprintf(g,"%d ", *it);
}
return 0;
}